Description
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a ‘desirability’ factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
- Line 1: Two space-separated integers: N and M
- Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
- Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6
1 4
2 6
3 12
2 7
Sample Output
23
题目链接
http://poj.org/problem?id=3624
题目翻译
有 N (1 ≤ N ≤ 3,402) 个物品，重量分别为 Wi (1 ≤ Wi ≤ 400)，价值分别为 Di (1 ≤ Di ≤ 100)。现在有一个承载重量最大为 M (1 ≤ M ≤ 12,880) 的箱子，求能放入箱子的物品的总价值最大为多少？
题目分析
01背包问题。
动态规划。
设res[i][j]表示在前 i 个物品中选择若干物品放入承载重量为 j 的箱子里，能放入的物品的总价值的最大值。
w[i] > j时，第 i 个物品不能放入承重为 j 的箱子中，易得res[i][j] = res[i-1][j]
w[i] <= j时，如果第 i 个物品不放入箱子，则res[i][j] = res[i-1][j]；如果第 i 个物品放入箱子，则res[i][j] = d[i] + res[i-1][j-w[i]]；所以有res[i][j] = max(res[i - 1][j], d[i] + res[i - 1][j - w[i]])
综上所述，我们得到了下面的递推关系式
if (j >= w[i])
res[i][j] = max(res[i - 1][j], res[i - 1][j - w[i]] + d[i]);
else
res[i][j] = res[i - 1][j];
我们会发现，res[i][j]只和下标比它小的res[i - 1][j]以及res[i - 1][j - w[i]]有关，所以我们可以使用两层循环将 res 数组所有的值都计算出来。
res[n][m]就是问题的答案。
但是，我们至少需要开一个3402 * 12880这么大的数组，很明显会超出内存限制。
我们发现，res[i][j]只和res[i-1]有关，所以我们可以将res数组的第一维去掉。在j < w[i]时的res[i][j] = res[i - 1][j]也可以直接不写了。
res[m]就是答案。
res[j] = max(res[j], res[j - w[i]] + d[i]);
但要注意，因为res[j]会受到res[j - w[i]]的影响，所以内层循环需要由大到小进行。
AC代码
#include <iostream>
using namespace std;
int res[13000] = {0}, w[3500], d[3500];
int main()
{
int i, j, n, m;
cin >> n >> m;
for (i = 1; i <= n; i++)
cin >> w[i] >> d[i];
for (i = 1; i <= n; i++)
for (j = m; j >= w[i]; j--)
res[j] = max(res[j], res[j - w[i]] + d[i]);
cout << res[m] << endl;
return 0;
}