常见背包类型有
- 恰好背包
- 普通背包（01背包）
- 多重背包
- 完全背包
- ……
背包问题
形如这种题型的问题，我们统称为背包问题，
背包问题是DP的入门，要好好学习。
读者可以先思考一下答案哦
1. 恰好背包和普通背包
恰好背包描述：求解将哪些物品装入背包，可使这些物品的总体积恰好等于背包容量，且总价值最大。
普通背包描述：求解将哪些物品装入背包，可使这些物品的总体积不超过 背包容量，且总价值最大。
2.完全背包和01背包
01背包：
完全背包：
为啥要放到一起讲呢？实际上，解法很相似。
01背包基本思路
代码:01:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1010;
int n,m,dp[maxn];
int main(void)
{
cin>>n>>m;
for(int i = 0;i < n;i++)
{
int v,w;
cin>>v>>w;
for(int j = m;j >= v;j--)dp[j] = max(dp[j],dp[j-v]+w);
}
cout<<dp[m];
}
|
完全：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1010;
int n,m,dp[maxn];
int main(void)
{
cin>>n>>m;
for(int i = 0;i < n;i++)
{
int v,w;
cin>>v>>w;
for(int j = v;j <= m;j++)dp[j] = max(dp[j],dp[j-v]+w);
}
cout<<dp[m];
}
|