LKS - Large Knapsack
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Just implement 0/1 Knapsack.
First line contains two integers K and N, where K in the maximum knapsack size and N is the number of items. N lines follow where ith line describes ith item in the form vi and wi where vi is the value and wi is the weight of ith item.
Output a single number - maximum value of knapsack. (All operations and the answer are guaranteed to fit in signed 32-bit integer.)
Time limit changed to 2s on 02.07.11.
Input: 10 3 7 3 8 8 4 6 Output: 11
K <= 2000000
N <= 500
Vi <= 10^7
Wi <= 10^7
TOP DOWN DP WITH MEMORY OPTIMISATION. :)
its getting internal error in c++ 5.1 while the same code got AC in c++ 4.3.2!!!
If you want to know how to do it in 0.0 time just look up best first branch and bound.
even O(k) space in java cannot get AC :(( any hint?
Was getting TLE but changing array type from long long to int, turned to AC. O(N*k) gets AC
Do only space optimisation but not time.First try WACHOVIA problem.
solved in 1.45s after optimizing. Can't understand how it can be solved in 0.00s. Can anyone explain how?
lots of optimization needed from memory to time complexity.... nice :)
Guys, can you help me? how to decrease memory for this problem? i using dynamic programming and it using large memory in Array...
I got TLE , just changed array type from long long to int and got AC :-O