背包问题总结【01，恰好/不超过，完全，多重，路径记录，应用】

有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是v[i]。

1.0-1 背包

求解将哪些物品装入背包可使价值总和最大,每种物品至多只能选择一件

dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值

dp[i][j]=max{dp[i-1][j-w[i]]+v[i] , dp[i-1][j]};

这里我们从j=V倒推回来的话可以优化成

dp[j]=max{dp[j] , dp[j-w[i]]+v[i]};

核心代码：

for（i=0;i<=V;i++）{
    dp[i] = 0;//初始化均为0
}
for（i=1;i<=n;i++）{
    for(j=V;j>=w[i];j--){//倒序更新,对于重量w[i]小于j的不作更新
        //choice[i][j] = true;//如需记录，则可另创一个辅助数组(详见下文)
        dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
    }
}

dp[V]即为最大的价值

2.恰好装满时

此时只需改变初始值，即

#define INF 0x7fffffff
for（i=1;i<=V;i++）{
    dp[i] = INF;//除dp[0]外，其余均初始化为无穷
}
dp[0] = 0;

同时在状态转移前需加判断，if (dp[j - w[i]] != INF) dp=……

可以这样理解：初始化的dp 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装的状态下被 “恰好装满” ，此时背包价值为0。其他容量的背包均没有合法的解，属于未定义的状态，所以都应该被赋值为 −∞ 。当前的合法解，一定是从之前的合法状态推得的

如果背包并非必须被装满，那么任何容量的背包都有一个合法解 “什么也不装”，这个解的价值为0,所以初始化时状态的值也就全部为0了。

3.完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件。每件费用是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这时候对于每件物品就不是放与不放的问题了，而是放0件、1件…….

dp[i][j]表示容量为ｊ的背包第i件物品是否要再一次放入所以我们要从0-Ｖ顺序循环

dp[i][j]=max{dp[i][j-w[i]]+v[i],dp[i-1][j]}(注意这里和01背包的区别，第i件物品可以多次放）

优化后：dp[j]=max{dp[j] , dp[j-w[i]]+v[i]};

核心代码：

for（i=1;i<=n;i++）{
      for(j=w[i];j<=V;j++){//注意到与一般背包相比，改变的只是遍历的顺序
          dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
      }
  }

dp[V]即为最大的价值

4.多重背包问题

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

因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。

拆分：多重背包问题限定了一种物品的个数，解决多重背包问题，只需要把它转化为0-1背包问题即可。比如，有2件价值为5，重量为2的同一物品，我们就可以分为物品a和物品b，a和b的价值都为5，重量都为2，但我们把它们视作不同的物品。

核心代码：

int k = n + 1;
for (int i = 1; i <= n; i++) {//拆分
    while (num[i] != 1) {
        weight[k] = weight[i];
        value[k] = value[i];
        k++;
        num[i]--;
    }
}

若对时间复杂度要求较高，则可采用以下的分解方法

int c = 1;
while(k-c>0){//对物品的数量k，拆分成1，2，4，8……
    k-=c;
    list[++ cnt].w = c * w;
	list[cnt].v = c * v; //拆分后的物品重量和价格均为组成改物品的质量与价格总和           
	c *= 2;
}
list[++ cnt].w = w * k;
list[cnt].v = v * k;

//接着对拆分后的所有物品进行0-1背包处理即可

附：记录所选路径

新增二维数组choice[i][j]，表示第i件物品是否已放入容量为j的背包

for（i=0;i<=V;i++）{
    dp[i] = 0;//初始化均为0
}
for（i=1;i<=n;i++）{
    for(j=V;j>=w[i];j--){
        choice[i][j] = true;//记录所选结果
        dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
    }
}

//输出
vector<int> arr;
int v = m, index = n;
while(v > 0) {
    if(choice[index][v] == true) {//若第index个物品已放入
        arr.push_back(w[index]);
        v -= w[index];//体积减去相应的值
    }
    index--;//在index-1个物品中继续寻找(从后往前)
}
for(int i = 0; i < arr.size(); i++) {
    if(i != 0) printf(" ");
    printf("%d", arr[i]);
}

背包问题小结

1.一维的0-1背包为什么逆序而完全背包为什么顺序?

保证更新f[j]时，f[ j - weight[i] ]是没有放入物品i时的数据,即f[ i - 1 ][ j - weight[i] ]，因为0-1背包每个物品至多被选一次。而完全背包中，每个物品可以被选无限次，那么状态f[i][j]正好可以由可能已经放入物品i的状态f[ i - 1 ][ j - weight[i] ]转移而来。所以，遍历顺序改为顺序时，就是完全背包问题，其余都不用变

2.完全背包和 01背包的区别仅在于状态更新时的遍历顺序。 01背包是逆序，完全背包是顺序

3.不超过容量和 恰好装满 的区别仅在于二者的初始化

前者全0，后者一维：除dp[0]为0外，其余dp[j]都是负无穷；二维：dp[i][0] = 0（第一列),其余全为0x80000000

4.0-1背包循环边界 i:[1,N]，j:[V,weight[i]]

1.0-1 背包

2.恰好装满时

3.完全背包问题

4.多重背包问题

附：记录所选路径

背包问题小结

更多背包问题