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
lvmbk93:
20160829 06:56:13
Good for beginer who the first learn dynamic programming algorithm :D 

thevillager:
20160601 13:59:04
Use DP and its done. AC .very simple problem. 

sanjay:
20160528 14:08:37
easy one :) 

Nipun:
20160209 20:32:41
My first dp, you f***rs!! I am the king of the world... yayayayay.... 

sudip_95:
20160128 07:23:20
just use memoization using recursive top down approach. AC at first attempt! :D 

theph0enix:
20160124 12:45:10
TLE with python3.4 and dp with both topdown/bottomup apprach.. :( Last edit: 20160219 11:16:33 

Alexander007:
20160122 18:21:54
Got TLE for top down. Any idea why?? 

Junaid:
20151216 08:15:27
DP rocks.....:p 

shirayuki_rin:
20151204 09:07:28
Does anyone know why I get WA? My submission ID is 15775271. Please help, as the forum is not available. 

anand__20:
20151018 20:53:26
did it using recursive approach first...got TLE...dp solution got AC in first attempt... 
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 