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.
Input
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
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.
Example
Input: 10 3 7 3 8 8 4 6 Output: 11
Constraints
K <= 2000000
N <= 500
Vi <= 10^7
Wi <= 10^7
hide comments
surayans tiwari(http://bit.ly/1EPzcpv):
2014-06-20 12:24:15
heyy i am again again getting wrong ans i tried every possible test case seriously i need help
|
|
heatOn:
2014-05-25 04:51:50
vectors are slow. Using vector gave TLE !!
|
|
mohit gupta:
2014-04-05 21:24:48
dont know y
|
|
californiagurl:
2014-03-16 08:12:01
a senior at my colg taught me this optimization,, which is why i'm probably not as excited about getting this right ....i've always solved DP problems with this optimization |
|
innovolt:
2014-03-10 15:05:43
fod and macho ques.....very gud optimiztion thanx to spoj and Shikhar Sharad |
|
CoNtRaDiCtIoN:
2014-01-28 19:47:38
enjoyed a lot upon doing this :)very happy |
|
Luka:
2014-01-26 07:10:14
SIGSEGV !!! :( |
|
Fendy:
2013-12-14 07:55:30
I tried to solve this using top-down knapsack DP, but I can't handle about the memory problem, can someone help me? thanks in advance |
|
SanchitK:
2013-12-13 18:36:39
my code shows segmentation error in spoj.please help
|
|
Ouditchya Sinha:
2013-10-23 11:33:14
@Ashish Tilokani : Congratulations!! 2.2M & 0.00s, was it magic? :)
|
Added by: | Ace |
Date: | 2013-06-24 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |