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
Shalin Shah:
2015-07-09 20:53:52
I changed my 'for' loop to a 'while' loop and it got ACed. Can anybody specify a reason for that? It was giving a TLE with a 'for' loop. Last edit: 2015-07-09 20:54:22 |
|
:.Mohib.::
2015-06-14 15:51:33
Nice one :) |
|
Saurabh Mishra:
2015-05-28 19:01:49
really .. a nice one ...thanks :) |
|
shikhargarg:
2015-05-14 19:09:04
Just optimize the space... i got ac with complexity of n*k :) |
|
anando_du:
2015-03-11 18:36:49
nice problem :) learned optimization ^_^ AC in 1st go :) |
|
n3gativ3:
2015-03-05 14:06:22
good one :) |
|
Sourabh Sarkar:
2015-03-01 22:39:37
Those getting segmentation fault declare the array globally! |
|
: : still coding -_- ::
2015-02-10 22:01:05
how can it be done in 0.00 time.i optimized my code..still getting 1.37 sec
|
|
Anubhav Balodhi :
2015-01-31 11:28:16
I always find knapsack interesting, no matter "whether my seniors tell me this optimization" or something new... ACed ^_^ |
|
Rajat De:
2015-01-27 16:30:22
My solution with fast input passed in 1.80 seconds , how can one do this in 0.00? |
Added by: | Ace |
Date: | 2013-06-24 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |