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?
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.
Input: 4 5 1 8 2 4 3 0 2 5 2 3 Output: 13
|Added by:||Nikola P Borisov|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: ERL JS NODEJS PERL 6 SCM chicken VB.net|
my first dp :)
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Pyramid cluster unavailable for now, all new submission to this problem (and any pyramid problem) rejected :-O
Baratheraja R N:
simliar problem: WACHOVIA
Great problem for beginners like me... :)
You can't take item more than once ?
.:: Pratik ::.:
Why are these problems in classical. should they not be in Tutorial mode?
Classical 0-1 Knapsack Problem.Last edit: 2009-02-28 05:49:36