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]}

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>

using namespace std;
const int maxn=100;

int n,V;
int f[maxn][maxn];
int w[maxn],p[maxn];

int main()
{
        while(scanf("%d%d",&n,&V))
        {
                if(n==0 && V==0)
                        break;
                for(int i = 0; i <= n; ++i)  
        {  
            w[i] = 0, p[i] = 0;  
            for(int j = 0; j <= n; ++j)  
            {  
                f[i][j] = 0;  
            }  
        } 
                for(int i=0;i<n;i++)
                        scanf("%d%d",&w[i],&p[i]);
                for(int i=1;i<=n;i++)
                {
                        for(int v=w[i];v<=V;v++)
                        {
                                f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+p[i]);
                        }
                        cout<<f[n][V]<<endl;
                }
        }
}

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)是超前的，即将来的可能）。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>

using namespace std;
const int maxn=100;

int n,V;
int f[maxn][maxn];
int w[maxn],p[maxn];

int main()
{
        while(scanf("%d%d",&n,&V))
        {
                if(n==0 && V==0)
                        break;

        memset(f, 0, sizeof(f));  
        memset(w, 0, sizeof(w));  
        memset(p, 0, sizeof(p)); 
        
                for(int i=0;i<n;i++)
                        scanf("%d%d",&w[i],&p[i]);
                for(int i=1;i<=n;i++)
                {
                        for(int v=V;v>=w[i];v++)
                        {
                                f[v] = max(f[v],f[v-w[i]]+p[i]); 
                        }
                        cout<<f[V]<<endl;
                }
        }
}