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
drago_codes:
20221218 04:18:28
Can someone tell some dp problems based on knapsack 

mig21_5121:
20210922 17:21:02
basic but important


compus:
20210615 22:03:30
ok 

dardev:
20200722 19:08:17
Don't use tabular approach. Solve it with recursive. Improve your intuition. 

manish_thakur:
20200428 16:23:25
dp with memoization! 

raman_111:
20200329 06:30:44
only hint is try bottom up aproach either you have to face tle or run time error for sure #happy_coding 

scolar_fuad:
20190509 19:38:58
basic dp try iterative dp to learn something new bcz everyone try with recursive 

souvikd_pro:
20190312 17:06:09
topdown dp accepted :). Next try PARTY 

mhds:
20190309 20:08:07
AC in one go 

moeentm:
20190214 13:36:11
Tseries is nothing but a ..... lasagna 
Added by:  Nikola P Borisov 
Date:  20081110 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 