1. 01背包
1.1 题目
有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
1.2 二维下的解法
通读题目，这道题应该考察动态规划算法，原因在于是求最优解即最大价值。
那么，我们从动态规划出发，剖析本题：
最优解是在背包容量为j的情况下装进一些特定物品的最大价值。我们不清楚要装哪些物品，所以dp数组的一个维度一定是物品的选取，但我们又不能随意选取物品，因为背包是有限的，所以我们又要考虑背包容量这个维度，最后才能给出最优解。
也就是说，dp数组应该包含两个维度，一个是物品的选取，一个是背包容量。所以定义：
dp[i][j]表示有前i个物品且在背包容量为j时的背包的最大价值
对于边界来说，如果背包容量为0，那么最优解一定是0；如果有0个物品，那么最优解也一定是0；dp数组其余的地方也是0。也就是说，dp数组初始化为0。
正序逆序皆可。
下面具体看一下dp数组的用法 。
当前背包容量不够（j < v[i]），没得选，因此前 ii个物品最优解即为前 i−1个物品最解
当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：
- 选：f[i][j] = f[i - 1][j - v[i]] + w[i]
- 不选：f[i][j] = f[i - 1][j]
- 我们的决策是如何取到最大价值，因此以上两种情况取 max() 。
#include<stdio.h>
#define N 1001
int v[N]; // 体积
int w[N]; // 价值
int dp[N][N]; // f[i][j], j体积下前i个物品的最大价值
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
int n, m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d %d",&v[i],&w[i]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(j < v[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
printf("%d",dp[n][m]);
return 0;
}
1.3一维下的解法
二维解法的物品选取的这个维度可以转化为对物品数据的不断读取，也就把dp数组的维度从二维降到了一维。
dp[j]代表在已有的物品下且背包容量为j的背包最大价值
初始化为0。
如果遍历为顺序的话，根据dp数组的含义，遍历到前i个物品时，前i-1个物品的某个物品可能被选多次。
例如，找背包容量为10的最优解。如果第一个物品容量为1，遍历到dp[10]的时候该物品装进了背包；现在第二个物品可以装了，遍历到dp[10]的时候，此时dp[10]=1,明显还可以装第一个物品。也就是说，dp[10]很可能将第1个物品用了两次，而题目说只能用一次。
如果是逆序的话就不会出现这种情况。
#include<stdio.h>
#define N 1001
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
int n,m,dp[N]={0};
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++) {
int v, w;
scanf("%d %d",&v,&w);
for(int j = m; j >= v; j--)
dp[j] = max(dp[j], dp[j - v] + w);
}
printf("%d",dp[m]);
}
2. 完全背包
01背包是物品只能被选一次，而完全背包下物品可以被选无限次。实际上二者只是存在对dp数组遍历顺序的差别，前者是逆序，后者是顺序。
2.1 题目
有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。
第 ii 种物品的体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
2.2 题解
#include<stdio.h>
#define N 1001
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
int n,m,dp[N]={0};
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++) {
int v, w;
scanf("%d %d",&v,&w);
for(int j = v; j <= m; j++)
dp[j] = max(dp[j], dp[j - v] + w);
}
printf("%d",dp[m]);
}
3. 多重背包
3.1 题目
有 NN 种物品和一个容量是 VV 的背包。
第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
3.2 题解
虽然每个物品的数量都不单一，但我们只需把几个相同的物品看成一个整体再用01背包处理。
#include<stdio.h>
#define N 101
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
int n,m;
int dp[N]={0};
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int u,w,s;
scanf("%d %d %d",&u,&w,&s);
for(int j=m;j>=u;j--)
{
for(int k=1;k<=s&&j>=k*u;k++)
{
dp[j] = max(dp[j],dp[j-k*u]+k*w);
}
}
}
printf("%d",dp[m]);
}
4. 分组背包
4.1 题目
有 NN 组物品和一个容量是 VV 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vijvij，价值是 wijwij，其中 ii 是组号，jj 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V,N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 NN 组数据：
- 每组数据第一行有一个整数 SiSi，表示第 ii 个物品组的物品数量；
- 每组数据接下来有 SiSi 行，每行有两个整数 vij,wijvij,wij，用空格隔开，分别表示第 ii 个物品组的第 jj 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000<N,V≤100
0<Si≤1000<Si≤100
0<vij,wij≤1000<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
4.2 题解
由于在每一组都最多选一个，那么对于一组而言可以用01背包处理，进而得到最优解。
#include<stdio.h>
#define N 110
int n, V;
int v[N], w[N];
int f[N];
int max(int a,int b)
{
return a>=b?a:b;
}
int main()
{
scanf("%d%d",&n,&V);
while(n --)
{
int s;
scanf("%d",&s);
for(int i = 0; i < s; i ++) scanf("%d%d",&v[i],&w[i]);
for(int i = V; i >= 0; i --)
for(int j = 0; j < s; j ++)
if(i >= v[j]) f[i] = max(f[i], f[i - v[j]] + w[j]);
}
printf("%d",f[V]);
return 0;
}
5. 总结
- 从不同的物品拿，每个物品最多拿一次，是01背包
- 从不同的物品拿，每个物品可拿无限次，是完全背包
- 从不同的物品拿，每个物品数量不同，是多重背包
- 从每组中最多拿一个物品，是分组背包
