小明的背包问题
小明的背包1 — — （01背包）
友情链接：小明的背包1
题目：
输入样例:
5 20 1 6 2 5 3 8 5 15 3 3输出样例：
37
思路：
对于01背包问题，其中一个重要的条件是每一种物品只有一个，因为在有n个物品v个容量的情况下的最大价值可以由它的子问题n - 1个物品v个容量的最大价值转化而来，因此我们可以利用动态规划的思想进行求解。
我们这样定义
dp数组：我们令dp数组的第一维表示每一个物品，dp数组的第二维表示背包的容量。如题目给出的样例，（一共有5个物品，背包的容量为20）我们可以得到如下的dp数组：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 2 3 4 5 对于第二维（即第一行数字）表示的是背包的容量，对于第一维（即第一列数字）表示的是物品的个数，背包的容量和物品的个数都是隐式存在的，并不是一个值，在程序中体现为下标（或索引）。
初始化
dp数组：对于背包容量为
0的情况，我们能放入的物品的个数为0个，因此初始化dp数组的第一列的值为0。对于物品个数为0的情况，能放入背包的物品的个数也为0个，因此我们初始化dp数组的第一行的值为0。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 3 0 4 0 5 0 递推公式：
对于每一行，即每一个物品来讲，如果当前的容量不能放入该物品，那么只能放入前面的物品，即当前容量能放入前面物品的最大价值，公式为：
dp[i][j] = dp[i - 1][j]，如果当前的容量能放入该物品，那么就尝试放入该物品，如果放入该物品后的价值更小，就不放入该物品，其值等于没有该物品的情况下当前背包的容量的最大价值，如果放入该物品后价值更大，就放入该物品。对应的公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i] + v[i]])，对于公式dp[i - 1][j - w[i] + v[i]]的理解是，首先每一个物品都是1个，因此要从之前的物品开始减去当前物品的体积（相当于取出一些物品，腾出恰好的空间，得到在背包容量为j - w[i]的情况下的最大价值），然后再放入当前的物品，得到放入当前物品后的价值。公式max(dp[i - 1][j], dp[i - 1][j - w[i] + v[i]])的意义是：对于第i件物品，可以放或者不放，具体取值我哪一种情况的价值更大。
代码：
// 01背包问题
#include<iostream>
#include<vector>
using namespace std;
int solve(){
int n,v;cin>>n>>v; // 物品数量和背包容量
vector<int> value(n + 1, 0);
vector<int> weight(n + 1, 0);
for(int i = 1;i <= n;i ++){
cin>>weight[i];
cin>>value[i];
}
// 进行动态求解
vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
dp[0][0] = 0;
for(int i = 1;i <= n;i ++){
dp[i][0] = 0;
}
for(int j = 1;j <= v;j ++){
dp[0][j] = 0;
}
// 递推
for(int i = 1;i <= n;i ++){ // 每一个物品
for(int j = 1;j <= v;j ++){ // 背包容量
if(j >= weight[i]){
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}else{
dp[i][j] = dp[i - 1][j]; // 不用在和dp[i][j - 1]进行比较了，与完全背包原因一致
}
}
}
cout<<dp[n][v]<<endl;
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
小明的背包2 — — （完全背包）
友情链接：小明的背包2
题目：
输入样例：
5 20 1 6 2 5 3 8 5 15 3 3输出样例：
120
思路：
多重背包问题与01背包问题的区别在于，多重背包的每一种物品都可以有无限多个，因此我们只需要再递推公式上进行略微修改即可。
我们定义一个二维的
dp数组，其含义与01背包定义的dp数组一样，第一维表示的是物品的种类，第二维表示的是背包的容量。对于给出的输入样例，可以建立一下的
dp数组。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 2 3 4 5 定义边界：
背包容量为0和物品种类为0对应的价值都是0，因此我们要将背包容量为0的一列以及物品种类为0的一行初始化为0。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 3 0 4 0 5 0 递推公式：
如果当前的容量不能放下该物品就继承自上一个物品再当前容量的
dp值，对应的公式：dp[i][j] = dp[i - 1][j]，可能有些小伙伴会有疑问，为什么不继承为max(dp[i - 1][j], dp[i][j - 1])呢？原因是：对于当前物品而言，如果不能放入，那么前一个容量自然也不能放入，依次类推到容量为0的情况，可以知道从0到当前情况每一个值都继承自当前容量的上一个物品的值，对于上一个物品而言，其值也是随着容量的增加而呈现出非严格单调递增的。所以使用公式：max(dp[i - 1][j], dp[i][j - 1])是没有意义的，当然最后的结果也是正确的，我们没有必要再进行一次额外的判断了。如果当前的容量能够放下该物品，就对应两种动作：放或不放，如果放的话就在当前容量的基础上减去该物品的体积，然后加上该物品的价值，如果不放就取上一个物品对应当前容量的价值，公式为：
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])，这里与01背包不同的是dp[i][j - w[i]] + v[i]，原因就在于完全背包问题可以对某一种物品放无限次，01背包只能对某一种物品放一次。
代码：
// 完全背包
#include<iostream>
#include<vector>
using namespace std;
int solve(){
int n,v;cin>>n>>v;
vector<int> value(n + 1, 0);
vector<int> weight(n + 1, 0);
for(int i = 1;i <= n;i ++){
cin>>weight[i];
cin>>value[i];
}
vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= v;j ++){
if(j >= weight[i]){
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
}else{
dp[i][j] = dp[i - 1][j]; // 不用在和 dp[i][j - 1] 进行比较了，因为如果放不下改为物品，那么之前的容量一定是取自上一个物品在当前容量的最大价值
}
}
}
cout<<dp[n][v]<<endl;
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
持续更新中…
![BugkuCTF：overflow2[WriteUP]](https://img-blog.csdnimg.cn/direct/511800f3066e459eb08b544632fd46ab.png)
