KNAPSACK - The Knapsack Problem

no tags 

The famous knapsack problem. You are packing for a vacation on the sea side and you are going to carry only one bag with capacity S (1 <= S <= 2000). You also have N (1<= N <= 2000) items that you might want to take with you to the sea side. Unfortunately you can not fit all of them in the knapsack so you will have to choose. For each item you are given its size and its value. You want to maximize the total value of all the items you are going to bring. What is this maximum total value?


On the first line you are given S and N. N lines follow with two integers on each line describing one of your items. The first number is the size of the item and the next is the value of the item.


You should output a single integer on one like - the total maximum value from the best choice of items for your trip.


4 5
1 8
2 4
3 0
2 5
2 3


hide comments
kimchiboy03: 2018-01-28 04:03:25

AC in one go!!!

mpiotrek: 2017-12-19 20:35:46

Remember to NOT write \n at the end :D

realife_playa: 2017-09-11 08:57:05

Should be the first problem for anyone attempting to learn Dynamic Programming.

nadstratosfer: 2017-08-31 11:00:53

With Python, top-down+memo -> RE, bottom-up -> TLE. Same with most of DP problems on this site. Better off bruteforcing with C than bother implementing correct algorithms in something else. Tutorial my ass.
Edit: Came back 2 months older, shuffled a few things around, got AC immediately. Still, correct algo shouldn't require optimization on every corner.

Last edit: 2017-11-18 10:26:38
dunjen_master: 2017-08-11 21:09:30

AC in one go
Try this its an extension to this

jskrnbindra: 2017-06-08 11:44:27

Last edit: 2017-06-08 11:44:47
da_201501181: 2017-05-20 09:29:14

Easy..!! AC in one GO..!!

suryansh_97: 2017-01-22 07:58:36

MY first DP the time has begun:-p

billoybillyboy: 2016-11-26 00:38:49

AC first go my 6th :D

Harshit Joshi: 2016-11-22 03:07:07

simple ques to practice basics....

Last edit: 2016-11-22 03:08:17

Added by:Nikola P Borisov
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET