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
Ashish Tilokani:
2013-10-23 08:27:42
fastest in c and most memory efficient in all!! |
|
Ashish Tilokani:
2013-10-23 08:24:29
the chances of my solution getting accepted was very low!! for some test cases my solution won't work for sure |
|
bigBOSS:
2013-08-27 09:25:07
nice prob....but dont know how to reduce the execution time...:( |
|
Ouditchya Sinha:
2013-08-02 05:18:41
Nice problem! Simple Twist of 0/1 Knapsack. :) |
|
Mostafa 36a2:
2013-07-19 13:27:10
Man ! implementing 0/1 Knapsack is far different than the easy fractional version ...
|
|
karan173:
2013-07-16 09:42:30
wow guys there's a trick!! |
|
Federico Lebrón:
2013-07-10 04:30:57
@Light Yagami: In general, cin and cout incur some overhead over scanf and printf. If the input is large, as it can be here (N lines, N somewhat large), scanf and printf will outperform cin and cout. Part of the slowness can be mitigated by calling cin.sync_with_stdio(false), and same with cout (be aware that C-style IO and C++-style IO will now be out of sync, don't try to use them together, they won't share a buffer or locks), but if you absolutely want the fastest, you can try replacing C++ style IO with C style IO. |
|
technophyle:
2013-07-05 01:01:04
OK now I got AC using int instead of long long since you mentioned that answer is going to fit in signed 32-bit integer.
|
|
BLANKRK:
2013-07-05 01:01:04
nice one.... :D got AC |
Added by: | Ace |
Date: | 2013-06-24 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |