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.
|
Sample Input |
Sample Output |
|
4 5 1 8 2 4 3 0 2 5 2 3 |
13 |
динамическое программирование
- рюкзак
Пусть m[j] – максимальная
стоимость товара, которого можно набрать в сумку вместимости j.
Реализация
алгоритма
#include <cstdio>
#include <vector>
using namespace std;
int i, j,
n, w;
int
weight, cost;
vector<int> m;
int main(void)
{
scanf("%d
%d",&w,&n);
m.assign(w+1,0);
for(i = 0; i < n; i++)
{
scanf("%d
%d",&weight,&cost);
for(j = w;
j >= weight; j--)
m[j] = max(m[j],m[j - weight] + cost);
}
printf("%d\n",m[w]);
return 0;
}