01，完全，多重，混合，分组背包相关题目

背包问题的状态定义基本都是：
在前i个物品选，体积不超过j的所有选法。属性可以是max， min， count

注意一点：背包问题基本都可以边读边进行dp运算。多这么写， 可以优化代码简洁度。

01背包

一维写法

#include 

using namespace std;

const int N = 1010;

int f[N][N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = 0; j <= m; j++)
            if(j >= v) f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w);
            else f[i][j] = f[i - 1][j];
    }
    
    cout << f[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二维写法
修改方法：

1. 把第1维删去
2. 如果当前状态由上一层状态得出， 体积循环就要倒着循环。因为f[j]可以由f[j - v]推导而来， 而j - v是小于j的，因此如果倒着循环的话，f[j - v]存放的还是上一次循环的值，因此是可行的。如果是正着循环，f[j] = f[j - v] + w, 而f[j - v]早就被这次循环的值覆盖了，因此不可行。

#include 

using namespace std;

const int N = 1010;

int f[N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }
    
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

完全背包

具体推导不写了， 很简单。把f[i][j - v]和f[i][j]的表达式比较一下即可。

很容易错的地方是：当背包放不下该物品的时候，f[i][j] = f[i - 1][j]，优化成一维后这行就变成了恒等式，因此不用写。但是f[i][j] = max(f[i-1][j], f[i][j - v] + w)只有在书包放的下的情况下才成立，因此一定要加上if！！！

二维写法：

#include 

using namespace std;

const int N = 1010;

int f[N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = 0; j <= m; j++)
            if(j >= v)
                f[j] = max(f[j], f[j - v] + w);
    }
    
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这里要说一下一维写法，因为从一维写法才可以看出为什么完全背包可以正在循环

#include 

using namespace std;

const int N = 1010;

int f[N][N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = 0; j <= m; j++)
        {
        	无论背包体积够不够，f[i][j]都必须有可能等于f[i - 1][j],因此
        	可以这么写
            f[i][j] = f[i - 1][j];
            if(j >= v) f[i][j] = max(f[i][j], f[i][j - v] + w);
			
			当然这么写也是可以的，但是这么写就看不出来为什么优化成一维后
			体积可以正着循环
			if(j >= v) f[i][j] = max(f[i - 1][j], f[i][j - v] + w)
			else f[i][j] = f[i - 1][j]
        }
    }
    
    cout << f[n][m];
}
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
31
32
33

我们可以发现，在这种写法下，f[i][j] = max(f[i][j], f[i][j - v] + w), 状态的转移并不需要上一层的状态，因此可以正着循环。

多重背包

注意要加上if判断即可。

暴力写法：

#include 

using namespace std;

const int N = 110;

int n, m;

int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s; k++)
                if(k * v <= j)
                    f[j] = max(f[j], f[j - k * v] + k * w);
    }
    
    cout << f[m];
}
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

二进制优化写法：
原理：二进制 + 一个常数可以表示任意实数。比如10可以用1 2 4三个二进制 + 一个3来表示。又比如20可以用1 2 4 8 +一个5来表示。

因此多重背包，每一个物品的个数可以被拆成若干个01背包。比如该物品有20个，可以拆成{v, w}, {2v, 2w}, {4v, 4w}, {8v, 8w}, {5v, 5w}五个01背包。

因此把任意实数R写成1 + 2 + 4 + … + 2^(n - 1) + c
条件是：2^(n) - 1 < R

代码:

#include 

using namespace std;

const int N = 1010;

int f[N];


int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2)
        {
        	k是当前01组的个数， 每次分配完一组，都可以开始计算dp了
        	每次分配完一组，都要将这组对应的个数减去，因此要s -= k
        	直到减到剩下物品没有办法凑成2的n次方了，证明到了最后一个数了
            for(int j = m; j >= k * v; j--)
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }
        
        如果最后一个数不为0，证明任意常数c不为0，分为最后一组
        if(s)
        {
            for(int j = m; j >= s * v; j--)
                f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }
    
    cout << f[m];
}
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
31
32
33
34
35
36
37
38

混合背包

混合背包指的是每一个物品个数可能只有1个，可能有无限个，可能有限个。
做法就是三种背包问题结合起来即可。

当然也可以把完全背包，01背包转换成多重背包。完全背包的物品个数等于总体积 / 单个物品的体积， 01背包的物品个数就是1.

代码：

#include 

using namespace std;

const int N = 1010;

int f[N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if(s == 0)
            for(int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        else
        {
            if(s == -1) s = 1;
            for(int k = 1; k <= s; k *= 2)
            {
                for(int j = m; j >= k * v; j--)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            
            if(s)
            {
                for(int j = m; j >= s * v; j--)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    
    cout << f[m];
}
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
31
32
33
34
35
36
37
38
39
40

分组背包

分组背包就不要一边读一边计算dp了。先把组分好了再计算会比较清晰。

#include 

using namespace std;

const int N = 110;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int ss;
        cin >> ss;
        for(int j = 1; j <= ss; j++)
        {
            int vv, ww;
            cin >> vv >> ww;
            v[i][j] = vv, w[i][j] = ww;
        }
        s[i] = ss;
    }
    
    
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s[i]; k++)
                if(v[i][k] <= j) 
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    
    cout << f[m];
}
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
31
32
33
34
35
36

采药

采药
这是一道裸01背包问题。
ac代码：

#include 

using namespace std;

const int N = 1010;

int f[N];

int n, m;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }
    
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

装箱问题

装箱问题
考点：01背包。题中要求剩余体积最小，也就是装入物品体积最大。我们可以把价值等同于体积来求01背包。

ac代码：

#include 

using namespace std;

int n, m;

const int N = 50;

int v[N], w[N], f[20010];

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++) cin >> v[i], w[i] = v[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        
    cout << m - f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

宠物小精灵之收服

宠物小精灵之收服

考点：二维费用的01背包。这道题如果没有深刻理解01背包的状态定义就很容易错。
1.01背包的状态定义是在前i个物品里面， 背包体积不超过j的所有选法集合。这里要明确，背包体积不超过j有花费背包体积不超过j的意思。

2.花费的概念很重要， 因为这题最后要你求在价值最大的情况下，皮卡丘的剩余体力最大。剩余体力最大也就是花费体力最小，也就是j最小的情况。

3.还有一点：皮卡丘的体力不可以为0， 我之前犯过的错误就是写成了0 < j <= m， 然而这是不正确的。j代表的是花费的体积而不是剩余的体积。因此正确答案应该是0 <= j < m， j不能等于m。一旦等于m代表皮卡丘花费的体力为m，那么剩余体力就是0了。不符合题意。

#include 

using namespace std;

int n, m, k;

const int N = 1010, M = 510, K = 110;

int f[N][M];

int main()
{
    cin >> m >> k >> n;
    for(int i = 1; i <= n; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        for(int u = m; u >= v1; u--)
            for(int j = k - 1; j >= v2; j--)
                f[u][j] = max(f[u][j], f[u - v1][j - v2] + 1);
    }
    
    cout << f[m][k - 1] << ' ';
    
    int res = 0;
   for(int i = 0; i <= k - 1; i++)
        if(f[m][i] == f[m][k - 1])
        {
            res = i;
            break;
        }
    cout << k - res;
}
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
31
32
33

数字组合

数字组合
考点：01背包求方案个数。也就是属性是count的情况
转移方程是:如果放得下的话：f[j] = f[j] + f[j - v]
初始化f[0] = 1， 因为要组合的数字是0的话，不需要任何数字都是一个方案。

ps：这种是恰好情况的01背包，之前做的大多数都是背包体积不超过j的01背包。之后还有背包体积不小于j的01背包。它们三个的状态转移方程是完全一样的，但是循环范围和初始化方式不同。且恰好情况一般求count，不超过情况一般求max，不小于情况一般求min

#include 

using namespace std;

const int M = 10010;

int f[M];

int n, m;

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int v;
        cin >> v;
        for(int j = m; j >= v; j--)
            f[j] = f[j] + f[j - v];
    }
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

买书

买书
考点：完全背包求方案数量。本质还是count属性
在放的下的情况下:f[j] = f[j] + f[j - v]

#include 

using namespace std;

int v[5] = {0, 10, 20, 50, 100};

int n;

const int N = 1010;
int f[N];

int main()
{
    cin >> n;
    
    f[0] = 1;
    for(int i = 1; i <= 4; i++)
        for(int j = v[i]; j <= n; j++)
            f[j] = f[j] + f[j - v[i]];
            
    cout << f[n];
}       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

货币系统

和买书是一模一样的题目。

#include 

using namespace std;

const int N = 3010;

long long f[N];

int n, m;

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int v;
        cin >> v;
        for(int j = v; j <= m; j++)
            f[j] += f[j - v];
    }
    
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

庆功会

考点：二进制优化多重背包裸题。

#include 

using namespace std;
const int N = 6010;

int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2)
        {
            for(int j = m; j >= k * v; j--)
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }
        
        if(s)
        {
            for(int j = m; j >= s * v; j--)
                f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }
    
    cout << f[m];
}
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

二维费用背包问题

和宠物小精灵那道题目差不多，考点都是二位费用的01背包问题。直接一维是体积，一维是重量即可。

#include 

using namespace std;

const int N = 110;

int f[N][N];

int n, m, k;

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
    {
        int v, w, ww;
        cin >> v >> w >> ww;
        for(int j = m; j >= v; j--)
            for(int u = k; u >= w; u--)
                f[j][u] = max(f[j][u], f[j - v][u - w] + ww);
    }
    
    cout << f[m][k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

潜水员

考点：求最小值的二维背包问题。
之前说过，不管是最小，最大，还是恰好，它们的转移方程都是一样的。但是循环范围和初始化不同。

有题意得状态定义是氧气体积不少于j， 氮气体积不少于k的所有选法。属性是min。
对于求min的背包问题，所有格子都要初始化成INF（不然求不了min）。f[0][0] = 0，因为氧气氮气体积不少于0，那么最小重量一定是0.

关于循环范围的问题。由于状态定义是体积不少于某个数，那么这个数若是负数的话，状态定义也是成立的。（不少于一个负数题目中所有情况都符合，但是负数索引会越界，因此不少于负数可以全部当成不少于0的状态，也就是最小重量为0）

循环范围： 求体积不超过j的时候，一定要注意放不下的情况，因此一般都是 j = m; j >= v; j–等等
求体积至少为j的时候，一定要注意负数是可行的，因此一般都是j = m; j >= 0; j–

#include 
#include 
using namespace std;

const int N = 100;

int n, m, k;
int f[N][N];

int main()
{
    cin >> n >> m >> k;
    
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for(int u = 1; u <= k; u++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        for(int i = n; i >= 0; i--)
            for(int j = m; j >= 0; j--)
                f[i][j] = min(f[max(0, i - v1)][max(0, j - v2)] + w, f[i][j]);
    }
    
    cout << f[n][m];
}
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

机器分配

机器分配
考点：分组背包+输出具体选择的方案

分组背包不再赘述，讲一讲怎么输出背包问题的具体方案。

关键操作在于倒推。加入f[i][j] = f[i-1][j-v] + w,则证明我选了当前的物品。若f[i][j] = f[i -
1][j]则证明没有选当前物品。
ps：求背包具体方案不能优化空间，因为要保存所有状态信息。优化了只有一层的状态了。无法倒推。

还要注意一点，m>=v[i][k]才可以继续倒推，背包体积一定要放得下这个物品才行。

#include 
#include 

using namespace std;

const int N = 20;

int f[N][N];
int v[N][N], w[N][N], s[N];

int n, m;

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            int ww;
            cin >> ww;
            v[i][j] = j, w[i][j] = ww;
        }
    }
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= m; k++)
                if(v[i][k] <= j)
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
    
    cout << f[n][m] << endl;
    
    for(int i = n; i >= 1; i--)
        for(int k = 0; k <= m; k++)
        {
            if(m >= v[i][k] && f[i][m] == f[i - 1][m - v[i][k]] + w[i][k])
            {
                cout << i << ' ' << k << endl;
                m -= v[i][k];
                break;
            }
        }
    
    
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

求背包问题的具体方案（输出字符串字典序最小）

求背包问题的具体方案
考点：求背包问题的具体方案，方法还是倒推。

由于这次要求字典序最小，因此要从第一件物品开始输出，然而我们是要倒推的。因此我们要让f[1][1]是最终的结果状态。f[n][m]是最初的状态。

因此倒着循环计算dp即可。

易错点：该物品要放得下才可以继续倒推！！！背包问题里面不要老是忘记加这个条件！！！

#include 
using namespace std;

const int N = 1010;

int f[N][N], V[N], W[N];

int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        V[i] = v, W[i] = w;
    }
    
    
    for(int i = n; i >= 1; i--)
    {
        for(int j = m; j >= 0; j--)
        {
            f[i][j] = f[i + 1][j];
            if(j >= V[i]) f[i][j] = max(f[i][j], f[i + 1][j - V[i]] + W[i]);
        }
    }
    int j = m;
    for(int i = 1; i <= n; i++)
    {
        if(j >= V[i] && f[i][j] == f[i + 1][j - V[i]] + W[i])
        {
            cout << i << ' ';
            j -= V[i];
        }
    }
}
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
31
32
33
34
35
36
37
38

物品是不同策略的背包问题

金明的预算方案
考点：用二进制枚举所有情况转换成分组背包的问题。

这题说的是：要买附件就必须先买主件。因此可以将买主件和附件排列组合一下。
比如：如果有两个附件一个主件，可以组合成四种情况

这四种情况可以是一组背包，每一个决策只能选一次，因为只有一个主件。这样就转换成分组背包问题了。

我们发现，策略的个数是2^(附件数量).因为每一个附件都有选和不选两种情况。

所以可以用二进制枚举所有情况：下面给出代码模板：

for(int k = 0; k < 1 << xx.size(); k++)所有情况.比如2^2 = 4
{
    for(int u = 0; u < xx.size(); u++)每种情况的选择对象，这里是2
    {
        if(1 << u & k)如果这一位是0代表不选，是1代表选
        {
            xxxxxxxx
        }
    }
   	xxxxxxx
}
1
2
3
4
5
6
7
8
9
10
11

ac代码：

#include 
#include 
using namespace std;

const int N = 32010, M = 100;

typedef pair<int, int> pii;

pii master[M];
vector<pii>servent[M];
vector<pii> group[M];
int f[N];

int n, m;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if(!s)
            master[i] = {v, v * w};
        else
            servent[s].push_back({v, v * w});
    }
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(master[i].first)
        {
            cnt++;
            for(int k = 0; k < 1 << servent[i].size(); k++)
            {
                int tmp_v = master[i].first, tmp_w = master[i].second;
                for(int u = 0; u < servent[i].size(); u++)
                {
                    if(1 << u & k)
                    {
                        tmp_v += servent[i][u].first;
                        tmp_w += servent[i][u].second;
                    }
                }
                group[cnt].push_back({tmp_v, tmp_w});
            }
        }
    }
    
    for(int i = 1; i <= cnt; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k < group[i].size(); k++)
                if(group[i][k].first <= j)
                    f[j] = max(f[j], f[j - group[i][k].first] + group[i][k].second);
    cout << f[m];
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57