本文为软件部2022届讲课底稿，作者5月份的时候决定出国，遂卷绩点和英语去了，本文诸多疏漏请多包涵，毕竟不是专业算法选手。

目录

背包问题的背景是什么

分组背包问题的背景

分组背包问题的分析

分组背包的代码

分组背包问题和多重背包问题的异同

问题：分组背包中的滚动数组遍历背包体积的方式为什么和01背包一样是逆序？

背包问题的背景是什么

现在有一个背包，体积是v，给定一些物品，这些物品有他们各自的体积vi，也有他们各自的价值权重wi，想要找出怎么装背包，才可以使背包里物品的总价值最大。

问题一：背包必须装满吗？

答：不是。 

分组背包问题的背景

现在手上有一个背包，给定 n 组物品组，每一组物品组里面都有一定数量的不同的物件。第i组物品组第j件物品的价值权重用w[i][j]来表示，体积用v[i][j]来表示。实际的图示如下。

分组背包问题的分析

分组背包的代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int s[N];//表示每一组的数量
int v[N][N],w[N][N];
//v[i][j]表示的是第i组里第j个物品的价值权重
int dp[N];
int n,m;
int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }

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

分组背包问题和多重背包问题的异同

相似点：y氏dp法分析的时候都是划分时候都是按照第i种物品的数量来进行的划分

不同点：

分组背包表示的是第i组物品选取哪一个，注意，一组里面只可以选一个，我们分析的是选取哪一个。

多重背包和完全背包表示的是第i种物品可以选多个，我们分析的是可以选几个。 

问题：分组背包中的滚动数组遍历背包体积的方式为什么和01背包一样是逆序？

首先，理解一个意识，一维滚动数组逆序代表的是动态规划方程的新式子是由上一层推导而来的，所以上一层的原有的值不可以被更新覆盖。

                   

一维滚动数组正序代表的是动态规划方程的新式子是由本层推导而来的，所以上一层的原有的值必须被更新覆盖。

 

然后，分组背包的公式推导如图，显然，用逆序。