0-1背包

有n个物品，每个物品都有两个属性：价值v和重量w。有一个容量为W的背包，现要求这些物品尽可能装进背包，并使得价值最大。

因为每种物品只有一个，选或者不选，因此也叫做0-1背包

记Res(i,j)为还有编号为1~i的物品可以选，背包剩余容量为 j 时所能获得的最大价值

很明显 Res(0,j) =0 ,因为还有0个物品可以选，将这0个物品放入还剩 j 容量的背包所能获得的价值当然为0

当还有1~i个物品可以选，背包容量为 j 时，对于编号为 i 的物品，只有两种选择：选或者不选

1、不选编号为 i 的物品，那么Res(i, j) = Res(i-1, j), 下一步只考虑前 i-1个物品，且背包容量不变

2、选编号为 i 的物品， 那么Res(i, j) = Res(i-1, j-w[i]) + v[i] ，下一步只考虑前 i-1个物品，因为已经选了编号为 i 的物品，则背包容量相应的减小w[i] ,总价值增加 v[i]

还有考虑一些细节：

1、边界条件：Res(0，j) = 0

2、j<w[i] , 背包所剩容量不足以放入编号为 i 的物品，Res(i, j) = Res(i-1, j)

所以可以得到方程：

                      0                                                           i = 0

Res(i ,j) =    Res(i-1,j)                                                 j<w[i]

                   max{Res(i-1, j) , Res(i-1, j-w[i])+v[i] }      other

递归程序：

 

#include
      
       #include
       
        using namespace std;int w[5] = {
    0,2,1,3,2};int v[5] = {
    0,3,2,4,2};int n = 4, W = 5;int Res(int i, int j){    if (i == 0)     //还剩0个物品        return 0;    else if (j < w[i]){  //剩余容量不足，不能选        return Res(i-1,j);    }    else{        return max(Res(i-1,j),Res(i-1,j-w[i])+v[i]);    }}int main(){    cout << Res(4,5) << endl;    return 0;}
       
      

 

 如果利用dp求解，将上述方程Res(i,j) 变成 dp[i][j]

dp程序：

 

#include
      
       #include
       
        #include
        
         using namespace std;int w[5] = {
    0,2,1,3,2};int v[5] = {
    0,3,2,4,2};int n = 4, W = 5;int dp[10][10];int main(){    memset(dp,0,sizeof dp);    for (int i = 1;i<=n; i++){   //从1开始，因为已经确定i=0时，dp=0        for (int j = 0; j <= W; j++){            if (j < w[i])          //背包容量不足                dp[i][j] = dp[i - 1][j];            else                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);        }    }    cout << dp[n][W] << endl;    return 0;}
        
       
      

 

空间优化：

从上面的方程可以看出，不管是选还是没被选，第i行的数据来自第i-1行，所以没必要开二维数组存表，只需要开两行不断更新就好了，因为算第i+1行的答案用不到第i-1行的数据

代码：

#include
      
       #include
       
        #include
        
         using namespace std;int w[5] = {
    0,2,1,3,2};int v[5] = {
    0,3,2,4,2};int n = 4, W = 5;int dp[10];int main(){    memset(dp,0,sizeof dp);    for (int i = 1;i<=n; i++){   //从1开始，因为已经确定i=0时，dp=0        for (int j = W; j>= 0; j--){   //容量递减            if (j < w[i])          //背包容量不足                dp[j] = dp[j];            else                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);        }    }    cout << dp[W] << endl;    //注意输出    return 0;}
        
       
      

 

再来看看初始化的细节：

背包问题一般有两种：

1、要求背包必须填满时的最优解

2、不要求背包必须填满，只要价值尽可能大就ok

我们上面讨论的就是第2种。

如果是第一种，则初始化dp[0]=0,dp[1~W] 为-∞

---

完全背包

 对于每个物品，可以选任意个

 

#include
       
        #include
        
         #include
         
          using namespace std;int n=3,W=7;int v[] = {
     0,4,5,3};int w[] = {
     0,3,4,2};int dp[10];int main(){    memset(dp, 0, sizeof dp);    for (int i = 1; i <= n; i++){        for (int j = 0; j <= W; j++){   //这里时升序，和0-1背包相反            if (j < w[i])                dp[j] = dp[j];            else                dp[j] = max(dp[j],dp[j - w[i]] + v[i]);        }    }    cout << dp[W] << endl;    return 0;}