KNAPSACK  The Knapsack Problem
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?
Input
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.
Output
You should output a single integer on one like  the total maximum value from the best choice of items for your trip.
Example
Input: 4 5 1 8 2 4 3 0 2 5 2 3 Output: 13
hide comments
richardks3647:
20180628 03:13:24
AC in one go 

aryan12:
20180616 19:01:17
AC in 1 go using DP. My first DP solution in SPOJ.


na0013:
20180616 16:29:01
AC in one go!!


k3rnelpan1c:
20180427 23:07:29
I have a dream that one day correct python solution won't get a TLE ! 

goodwilllion:
20180226 09:27:26
AC IN ONE GO!!!


kimchiboy03:
20180128 04:03:25
AC in one go!!! 

mpiotrek:
20171219 20:35:46
Remember to NOT write \n at the end :D 

realife_playa:
20170911 08:57:05
Should be the first problem for anyone attempting to learn Dynamic Programming. 

nadstratosfer:
20170831 11:00:53
With Python, topdown+memo > RE, bottomup > 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.


dunjen_master:
20170811 21:09:30
AC in one go

Added by:  Nikola P Borisov 
Date:  20081110 
Time limit:  0.240s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 