概述

嗯……背包问题是什么？

背包问题，是动态规划问题中的典型的一类。顾名思义，是跟背包有关的问题（竟然和名字有关，爷青结）。

大概就是讲背包空间有限，怎样合理地装物品可以让总价值最高的问题。

其实也不是非常难。

本文讲哪几类？

背包问题的主要难点也就在于种类繁多，需要记忆各种递推公式、循环结构。

不过毕竟是记忆而已，总是比其他需要现场推倒递推公式的要好不少。

本文主要讲以下几类：

01背包问题

完全背包问题（目前只讲前两种，后面的以后慢慢更新，毕竟所有背包都是以这两种为基础的）（后面的题目已经写好，以后讲解）

多重背包问题

二维费用背包问题

分组背包问题

01背包问题

题目

题目描述

一个旅行者有一个最多能装 MM 公斤的背包，现在有 nn 件物品，它们的重量分别是W1，W2，...,WnW1，W2，…,Wn,它们的价值分别为C1,C2,...,CnC1,C2,…,Cn，求旅行者能获得最大总价值。

输入

第一行：两个整数，MM(背包容量，M≤200M≤200)和NN(物品数量，N≤30N≤30)；

第2..N+12..N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

输入样例

10 4
2 1
3 3
4 5
7 9

输出样例

12

讲解

既然要用用动态规划法解决0-1背包问题，我们就先定义动态规划的三个要点，即状态、状态转移方程和边界条件。

首先我们用子问题定义状态，我们用F(i,j)表示“把前i件物品放入容量为j的背包中的最大总重量”。

然后我们要考虑怎样的状态转移方程可以把这个问题转化为更小的子问题。我们依然以“每一个物品都有放或不放两种选择”的策略为基础，考虑第i件物品，如果我们选择不放第i件物品，那么问题就直接转化为“把前i-1件物品放入容量为j的背包中的最大总重量”，如果我们选择放第i件物品，那么问题就转化为“把前i-1件物品放入容量为j-V[i]的背包中的最大总重量加上第i件物品的重量”（这里值得注意的一点是，如果j-V[i]<0，即放入第i件物品后超过了背包容量的限制，那么我们就只能选择不放第i件物品了）。所以状态转移方程为F(i,j)=max{F(i-1,j),F(i-1,j-V[i])+W[i]}。

边界条件则很容易得到，i=0时F(i,j)为0（没有物品就没有重量），j<0时F(i,j)为负无穷（但在代码中并不会这样初始化，我们在j-V[i]<0时不计算第二种情况即可）。最终答案则是f(n,C)。
但其实这个空间复杂度是可以优化的。

可以直接用f[i]来表示当重量为i时，可以有的最大价值。

状态转移方程：

f[j] = max(f[j], f[j-c[i]]+w[i])

到了这里，终于要讲循环顺序的问题了。

其实第二层循环为什么要反向的问题，我也研究了好久，终于在看一篇文章的时候恍然大悟。

根据题意，每种物品只有一件。

当我们循环的时候，如果正序，那自然就会从前到后的更新数组。

那如果背包容量大于某件物品的多倍呢？

而恰好这件物品性价比很高？

假设a是一个常数。这件物品的质量为w。

那么，比如说，我们在循环到i=a的时候，把这件物品装进了背包。

那再循环到i=a+w的时候，可能又会把这件物品装进背包。

也就是说，这件物品被使用了两次，甚至后面可能更多。

而根据题意，每件物品只有一个。

而对于每一次更新，只会用到i比当前小的数据，而不会用到i比当前大的。（因为要查看f[i-w[j]],w[j]不可能是负的）

所以，先把大的更新了是没有问题的。

（学了背包问题这么久，终于把这个问题解决了！！！开心！！！）

核心代码：

#include <iostream>
#include <cstdio>
#define M 1000

using namespace std;

int f[M], c[M], w[M];
int ans, v, m;

int main() 
{
    scanf("%d%d", &v, &m);
    for(int i = 1; i <= m; i++)
    { 
        scanf("%d%d", &c[i], &w[i]);
    } 
    for(int i = 1; i <= m; i++)
    { 
        for(int j = v; j >= c[i]; j--) 
        {
            f[j] = max(f[j], f[j-c[i]]+w[i]);
        }
    } 
    printf("%d\n", f[v]);
    return 0;
}

完全背包问题

题目

题目描述

设有nn种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为MM，今从nn种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于MM，而价值的和为最大。

输入

第一行：两个整数，MM(背包容量，M≤200M≤200)和NN(物品数量，N≤30N≤30)；

第2..N+12..N+1行：每行二个整数Wi,CiWi,Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

输入样例

10 4
2 1
3 3
4 5
7 9

输出样例

max=12

#include <iostream>
#include <cstdio>
#define M 1000

using namespace std;

int f[M], c[M], w[M];
int ans, v, m;

int main() 
{
    scanf("%d%d", &v, &m);
    for(int i = 1; i <= m; i++)
    { 
        scanf("%d%d", &c[i], &w[i]);
    } 
    for(int i = 1; i <= m; i++)
    { 
        for(int j = c[i]; j <= v; j++) 
        {
            f[j] = max(f[j], f[j-c[i]]+w[i]);
        }
    } 
    printf("max=%d\n", f[v]);
    return 0;
}

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

1040

#include <bits/stdc++.h>
#define M 1000

using namespace std;

int f[M], c[M], w[M],num[M];
int ans, v, m;

int main()
{
        scanf("%d%d", &v, &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &c[i], &w[i],&num[i]);
        }
        int jjc=m;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= num[i]; ++j)
            {
                c[jjc]=c[i];
                w[jjc]=w[i];
                jjc++;
            }
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = c[i]; j <= v; j++)
            {
                f[j] = max(f[j], f[j-c[i]]+w[i]);
            }
        }
        printf("max=%d\n", f[v]);
        return 0;
}

10 100 5
7 10
2 40
2 50
1 20
4 20

3 30

10 100 5

8 110

12 10

20 10

5 200

1 110

0 100

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

20