[动态规划] 分组背包-Toy模板网

这篇具有很好参考价值的文章主要介绍了[动态规划] 分组背包。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

[动态规划] 分组背包,算法

开局思路

1.对dp[N] 的涵义进行定义

2.递推公式

3.初始化（此题不用）

4.遍历

1.dp[i][j]的定义：从1 - n组的物品里选出总体积不超过j的总价值。

2地推公式：dp[i][j] = max(dp[i][j], dp[i-1][j - v[i][k]] + w[i][k]);

[动态规划] 分组背包,算法如若装入遍历到的物品时最大值没发生变化则不变

[动态规划] 分组背包,算法

v[i][k] : 第i组中第k个物品的体积

w[i][k]; 该物品的价值

3. 略

4.先对组数 i 进行遍历，后对背包容量遍历，后对各个组中的单个物品遍历，

其中要判断该物品是否放得进当前容量的背包。

``` c++

for(int i = 1; i <= n; i++){
       for(int j = m; j >= 0; j--){ //背包容量遍历
           for(int k =1; k <= s[i]; k++){
               if(j >= v[i][k]){//判断是否装得下

```文章来源地址https://www.toymoban.com/news/detail-832497.html

背包遍历从大到小的原因:

dp[i][j] = max(dp[i][j], dp[i-1][j - v[i][k]] + w[i][j])

可等同于 dp[j] = max(dp[j], dp[j - v[i][k] + w[i][j])

由去掉的下标知 a第i层 b第i层, c第i -1层

我们可以从下标知道 c比a先算出来而a算的时候已经是第i层了。

因此从小到大遍历时c已经不是第i-1层而是第i层，而倒着算（遍历）可以避免这个问题。

最后遍历输出

```

#include<bits/stdc++.h>

using namespace std;

const int N =110;

int n, m, s[N];
int dp[N], v[N][N], w[N][N];

int main(){
   cin >> n >> m;

   for(int j = 1; j <= n; j++){
       cin >> s[j];
       for(int i = 1; i <= s[j]; i++){
           scanf("%d%d",&v[j][i],&w[j][i]);
       }
   }


   // dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][k]] + w[i][k])

   // dp[j] = max(dp[j], dp[j - v[i][k] + w[i][k]) 上一层为 i-1 从大到小排
   for(int i = 1; i <= n; i++){
       for(int j = m; j >= 0; j--){
           for(int k =1; k <= s[i]; k++){
               if(j >= v[i][k]){
                   dp[j] = max(dp[j],dp[j - v[i][k]] + w[i][k]);
               }
           }
       }
   }

   cout << dp[m];

   return 0;
}