POJ3624 0-1背包(dp+滚动数组)

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 W_i (1 ≤ W_i ≤ 400), a ‘desirability‘ factor D_i (1 ≤ D_i ≤ 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.

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: W_i and D_i

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

 1 #include 2 #include 3 #include
 4 using namespace std;
 5 int main()
 6 {
 7     int n, m;
 8     int d[13010], w[13010];
 9     int dp[13010];//因为求解该行时只与上一行有关，所以可以用滚动数组，dp[j]表示前i个物品在不超过体积j的最大价值
10     cin >> n >> m;
11     for (int i = 1; i i)
12     {
13         cin >> d[i] >> w[i];
14     }
15     memset(dp, 0, sizeof(dp));
16     for (int i = 1; i i)
17     {
18         for (int j = m; j >= 1; --j)//从右往左求解，把新求出的值保存在上面的位置，因为被覆盖的值只与它下面和下一行的右边有关
19         {
20             if (j >= d[i])
21                 dp[j] = max(dp[j], dp[j - d[i]] + w[i]);
22             else       //如果j-d[i]
23                 break;//又因为从右往左求值，左边的j只会更小，因此可跳过节省时间
24                         
25         }
26     }
27     cout  endl;
28     return 0;
29 }