004:0-1背包问题（DP）

Messj

注明：本题及讲解转载自 http://blog.csdn.net/hearthougan/article/details/53869671


题目：有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 w[i]，价值是 p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

不妨设集合

                               
登录/注册后可看大图

表示n个物品，该问题的某一个最优解集合为

                               
登录/注册后可看大图

。
1、最优子结构
       我们已经假设该问题的最优解为A，那么对于某个物品

                               
登录/注册后可看大图

，令S1=S-aj,V1=V-wj表示原问题除去物品后的一个子问题，那么,A1就是该子问题的一个最优解。可反证此问题，即存在一个A1'是子问题的最优解解，那么,所得的集合S'=A1'+aj一定比原问题最优解集合S所得的最大价值要大，这与假设矛盾。因此原问题的最优解一定包含子问题的最优解，这就证明了最优子结构性质。
2、递归地定义最优解的值
      对于每个物品我们可以有两个选择，放入背包，或者不放入，有n个物品，故而我们需要做出n个选择，于是我们设f[i][v]表示做出第i次选择后，所选物品放入一个容量为v的背包获得的最大价值。现在我们来找出递推公式，对于第i件物品，有两种选择，放或者不放。
  <1>:如果放入第i件物品，则f[i][v] = f[i-1][v-w[i]]+p[i],表示，前i-1次选择后所选物品放入容量为v-w[i]的背包所获得最大价值为f[i-1][v-w[i]]，加上当前所选的第i个物品的价值p[i]即为f[i][v]。
  <2>:如果不放入第i件物品，则有f[i][v] = f[i-1][v],表示当不选第i件物品时，f[i][v]就转化为前i-1次选择后所选物品占容量为v时的最大价值f[i-1][v]。则:
f[i][v] = max{f[i-1][v], f[i-1][v-w[i]]+p[i]}

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<iostream>
   
4. #include<cstring>
   
5. 
   
6. using namespace std;
   
7. const int maxn=100;
   
8. 
   
9. int n,V;
   
10. int f[maxn][maxn];
    
11. int w[maxn],p[maxn];
    
12. 
    
13. int main()
    
14. {
    
15.         while(scanf("%d%d",&n,&V))
    
16.         {
    
17.                 if(n==0 && V==0)
    
18.                         break;
    
19.                 for(int i = 0; i <= n; ++i)  
    
20.         {  
    
21.             w[i] = 0, p[i] = 0;  
    
22.             for(int j = 0; j <= n; ++j)  
    
23.             {  
    
24.                 f[i][j] = 0;  
    
25.             }  
    
26.         }
    
27.                 for(int i=0;i<n;i++)
    
28.                         scanf("%d%d",&w[i],&p[i]);
    
29.                 for(int i=1;i<=n;i++)
    
30.                 {
    
31.                         for(int v=w[i];v<=V;v++)
    
32.                         {
    
33.                                 f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+p[i]);
    
34.                         }
    
35.                         cout<<f[n][V]<<endl;
    
36.                 }
    
37.         }
    
38. }

复制代码

3.优化空间复杂度
上述解法的时空复杂度皆为O(VN）。时间复杂度无法再优化，但可以优化空间复杂度到O(V).
新的f[v]依赖 上一次的 f[v]和上一次的f[v-w[i]]，同理，新的f[v-1]依赖 上一次的 f[v-1]和上一次的f[v-1-w[i]],以此类推;如果是递增顺序计算，则上一次的f[v-w[i]]会被新的f[v-w[i]]覆盖。如果递减，则可以看到被覆盖的数f[v]对于下一个计算f[v-1]而言，是无法造成影响的（这是由于f(v)相对于f(v-1)是超前的，即将来的可能）。

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<iostream>
   
4. #include<cstring>
   
5. 
   
6. using namespace std;
   
7. const int maxn=100;
   
8. 
   
9. int n,V;
   
10. int f[maxn][maxn];
    
11. int w[maxn],p[maxn];
    
12. 
    
13. int main()
    
14. {
    
15.         while(scanf("%d%d",&n,&V))
    
16.         {
    
17.                 if(n==0 && V==0)
    
18.                         break;
    
19. 
    
20.         memset(f, 0, sizeof(f));  
    
21.         memset(w, 0, sizeof(w));  
    
22.         memset(p, 0, sizeof(p));
    
23.         
    
24.                 for(int i=0;i<n;i++)
    
25.                         scanf("%d%d",&w[i],&p[i]);
    
26.                 for(int i=1;i<=n;i++)
    
27.                 {
    
28.                         for(int v=V;v>=w[i];v++)
    
29.                         {
    
30.                                 f[v] = max(f[v],f[v-w[i]]+p[i]);
    
31.                         }
    
32.                         cout<<f[V]<<endl;
    
33.                 }
    
34.         }
    
35. }

复制代码