你有一个背包，最多能容纳的体积是 V。
现在有 n 种物品，每种物品有任意多个，第i种物品的体积为 vi ,价值为 wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数 n 和 V，表示物品个数和背包体积。
接下来 n 行，每行两个数 vi 和 wi，表示第 i 种物品的体积和价值。
且 1 ≤ n，V ≤ 1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：2 6
5 10
3 1
输出：10
2示例2
输入：3 8
3 10
9 1
10 1
输出：20
0
说明：无法恰好装满背包。第一问解题思路
这道题是 完全背包的模板题，题目看起来和 01背包 问题很像，其实唯一的区别就是题目中提到了每种物品有任意多个，说明一个物品是可以不选或者被多次选择的，而 01背包 问题中的物品就只有两种情况，也就是选一次或者不选。
而其余步骤其实和 01背包 是一模一样的，下面还是五部曲走起！
状态表示
根据 ”经验 + 题目要求“，定义状态表示为 dp[i][j] 表示在前 i 个元素中选，总体积不超过 j 即不超过当前背包空间，此时背包中物品的最大价值！
状态转移方程 -- 数学替换优化
状态转移方程稍微不太一样，因为完全背包问题多了很多种情况，一个物品不选、选一次、选两次、……、选 k 次，直到背包装不下。
虽然这种一个一个枚举的方法可以，但是时间复杂度就高啦，还记得之前写的 44. 通配符匹配 这道题吗，也是有很多种情况，当时的优化做法就是用数学替换，其实对完全背包来说，同样如此！
下面我们先列举出所有的状态可能：（这里就不细讲具体状态如何来的，可以参考 01背包 的讲解！）
可以看到，如果我们不对其稍加优化的话，那么情况其实非常多的，尤其是数据量如果很大的情况，所以我们必须要优化优化！
我们发现它们这些 dp 值推导其实是有点规律的，一般我们在数学替换的时候，都要找到能替换大部分相同部分的一个表达式，而这里符合条件的其实就是 dp[i][j - v[i]]，下面我们来看看为何符合：
初始化
开辟虚拟行列，然后全部初始化为 0 即可！
因为只用到上一行的数据，所以考虑第一行初始化即可！第一行表示不选物品，此时最大价值肯定为 0。
而第一列则跟着状态转移方程去填表完成即可！
填表顺序
从上往下，从左往右遍历！
返回值
根据状态表示，返回 dp[n][V]。
第二问解题思路
第二问无非就是在第一问上稍加修改，添加一些限定条件即可，这跟 01背包 问题的模板题是差不多的！
状态表示修改
dp[i][j] 表示在前 i 个元素中选，所选物品总体积正好等于 j 即正好等于背包空间，此时背包中物品的最大价值！
状态转移方程修改
依然是需要数学替换的，但是和第一问不一样的是我们还需要多做点处理，因为我们需要判断当前选了物品之后，是否会等于背包空间大小，如果不等于背包空间的话说明肯定没戏了，则让当前 dp 值为 -1。（具体为什么不是 0 也在之前讲 01背包 的时候说过了，可以去参考参考！）
也就是说我们用 -1 表示当前位置无法构成物品体积达到背包空间的要求！
并且我们只需要对选物品的时候做判断即可，对于不选物品的情况，此时是肯定成立的，直接让其赋值为 dp[i - 1][j]，如果 dp[i - 1][j] 就是不成立的，当前的值还是 -1，所以我们不需要担心！
初始化修改
初始化就不像我们上一问那样子直接初始化为 0 了，因为我们还多了个状态 -1，并且状态表示也变了，初始化的解析如下图所示：
返回值修改
还要注意的是，因为我们多设定了一个状态为 -1，但是题目要求不存在的时候返回 0，所以我们还需要判断如果为 -1 就返回 0 才正确！
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main()
{
// 填入数据
cin >> n >> V;
for(int i = 1; i <= n; ++i)
cin >> v[i] >> w[i];
// 解决第一问：求这个背包至多能装多大价值的物品
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= V; ++j)
{
dp[i][j] = dp[i - 1][j];
if(j >= v[i])
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
// 解决第二问：若背包恰好装满，求至多能装多大价值的物品
// 先清空dp表
memset(dp, 0, sizeof dp);
// 初始化第一行除了第一个元素之外的元素为-1
for(int j = 1; j <= V; ++j)
dp[0][j] = -1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= V; ++j)
{
dp[i][j] = dp[i - 1][j];
if(j >= v[i] && dp[i][j - v[i]] != -1)
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}💥优化
所有的「背包问题」，都可以进行空间上的优化。
对于 完全背包 类型的，我们的优化策略是：
- 删掉第一维
是的，我们不需要去关心
j的遍历顺序了，因为之前要考虑的原因是因为 01背包 的状态转移方程中涉及到dp[i - 1][j - v[i]]，而这里则不需要用到i-1行，反而省功夫了！
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main()
{
// 填入数据
cin >> n >> V;
for(int i = 1; i <= n; ++i)
cin >> v[i] >> w[i];
// 解决第一问：求这个背包至多能装多大价值的物品
for(int i = 1; i <= n; ++i)
for(int j = v[i]; j <= V; ++j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
// 解决第二问：若背包恰好装满，求至多能装多大价值的物品
// 先清空dp表
memset(dp, 0, sizeof dp);
// 初始化第一行除了第一个元素之外的元素为-1
for(int j = 1; j <= V; ++j)
dp[j] = -1;
for(int i = 1; i <= n; ++i)
{
for(int j = v[i]; j <= V; ++j)
{
if(dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
