分组背包问题（动态规划法）_分组背包问题 动态规划

1、问题描述：

2、解决思路

（1）思路：一般动态规划问题难就难在思路难以理解，一旦思路理解了代码非常好写，一般的动态规划题目我们可以分成两部分思考，一是问题的每一种状态如何表示，另一部分是如何从一个状态转移到另一个状态，也就是列出状态转移方程。

（2）状态转移方程：

当第i组物品选0个也就是一个都不选的时候，其实就与从前i-1组物品选，且总体积不大于j的最大价值等价；
而当从第i组选择第k个物品时，可以由在前i-1组物品里选，总体积不大于j减去第i组的第k个物品的体积的最大价值再加上第i组的第k个物品的价值得到。

故可以得到状态转移方程为：

3、代码

//1、朴素动态规划做法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
//f[i][j]表示从前i组物品选体积不大于j的最大价值
//s[i]表示第i组物品数量,v[i][k]、w[i][k]分别表示第i组第k个物品体积和价值
int f[N][N],v[N][N],w[N][N],s[N],n,m;

int main()
{
    scanf("%d%d",&n,&m);//输入物品组数n、背包体积m
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);//输入该组物品数量
        for(int j=1;j<=s[i];j++)
        {
            scanf("%d%d",&v[i][j],&w[i][j]);//输入该组每个物品的体积和价值
        }
    }
    for(int i=1;i<=n;i++)//遍历前i组物品
        for(int j=0;j<=m;j++)//体积从0开始遍历
        {
            f[i][j]=f[i-1][j];//记录不选第i组物品且体积不大于j的最大价值
            for(int k=1;k<=s[i];k++)//依次遍历第i组物品选哪一个
                if(j>=v[i][k])f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
        }
    printf("%d\n",f[n][m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4、时\空复杂度分析

（1）时间复杂度：
三重循环，故时间复杂度为：
其中n表示物品组数，V表示背包体积，S表示每组物品的数量。
（2）空间复杂度：
用二维数组存每个物品的体积和价值，故空间复杂度为：