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
Java: NZEC may mean you need memory-optimized DP (essentially == MLE).
i got AC one year ago , now i submit the same code , it give runtime error (SIGKILL) ?!!!!
I got acc in one go
my fst day of learning knapsack and accepted in one go!!
use int instead of long long int
AC in first submission
AC in one go :-) !!!!
Memoized. Got AC in one go ! :D
For all of you wondering how to get 0.0s learn branch and bound algorithm very useful and fun
*Edit: nevermind, i used a different compiler and it was fine.