POJ 3624 -- Charm Bracelet (0/1 Knapsack)

POJ 3624 -- Charm Bracelet (0/1 Knapsack)

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 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.

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: W_i and D_i

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://blog.csdn.net/lihao21/article/details/6227445
Slyar.
Slyar:标准的01背包，动态转移方程如下。其中dp[i,j]表示的是前i个物品装入容量为j的背包里所能产生的最大价值，w[i]是第i个物品的重量，d[i]是第i个物品的价值。如果某物品超过背包容量，则该物品一定不放入背包，问题变为剩余i-1个物品装入容量为j的背包所能产生的最大价值；否则该物品装入背包，问题变为剩余i-1个物品装入容量为j-w[i]的背包所能产生的最大价值加上物品i的价值d[i]

1. if (w[i]>j)   
2.     dp[i,j] = dp[i-1,j]  
3. else  
4.     dp[i,j] = max(dp[i-1,j-w[i]]+d[i],dp[i-1,j])  

先上一个用二维数组求解的代码，这个代码比较容易理解。

1. int main()  
2. {  
3.     int n, m;  
4.     cin >> n >> m;  
5.   
6.     /*从下标1开始存放*/  
7.     for(int i = 1; i <= n; i++) {  
8.         cin >> w[i] >> d[i];  
9.     }  
10.   
11.     /*注意，i==1或者j==1时，会用到dp边界下标为0的元素，由于已经初始化这些元素为0，保证了程序的正确运行*/  
12.     for(int i = 1; i <= n; i++) {  
13.         for(int j = 1; j <= m; j++) {  
14.             if(w[i] <= j)  
15.                 dp[i][j] = max(dp[i-1][j-w[i]] + d[i], dp[i-1][j]);  
16.             else  
17.                 dp[i][j] = dp[i-1][j];  
18.         }  
19.     }  
20.   
21.     cout << dp[n][m] << endl;  
22.   
23.     return 0;  
24. }  

由于OJ上memory所限，上面代码提交上去会MLE的。在纸上计算dp过程中，发觉dp设置成n行的二维数组实际上没有必要，因为在计算dp第i行时只用到dp第i-1行的数据，而且到了最后，前面n-1行都没用的。因此，完全可以用一维数组进行计算。但要注意，应从后住前计算dp，否则dp的数据会被新计算的值覆盖，导致不正确。

1.     for(int i = 1; i <= n; i++) {  
2.         for(int j = m; j >= 1; j--) {  
3.             if(w[i] <= j)  
4.                 dp[j] = max(dp[j-w[i]] + d[i], dp[j]);  
5.             else  
6.                 dp[j] = dp[j];  
7.         }  
8.     }  

观察二重for循环，可以发觉其实还可以继续进一步优化下

1.     for(int i = 1; i <= n; i++) {  
2.         for(int j = m; j >= w[i]; j--) {  
3.             dp[j] = max(dp[j-w[i]] + d[i], dp[j]);  
4.         }  
5.     }  
6.   

Read full article from 3624 -- Charm Bracelet