01背包理论基础
46. 携带研究材料（第六期模拟笔试） (kamacoder.com)
01 背包
有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
二维dp数组01背包：i 来表示物品、j表示背包容量。
定义：表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式： 考虑能不能放下
初始化：时全为零；时，时，其他
1
2
3
4
5
6
| for (int j = 0 ; j < weight[0]; j++) {
dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
|
进一步改进，直接数组初始化为零
1
2
3
4
5
| vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
|
遍历顺序: 先物品后背包，先背包后物品均可
1
2
3
4
5
6
7
| for(int i = 1; i < weight.size(); i++) {
for(int j = 0; j <= bagweight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
|
1
2
3
4
5
6
| for(int j = 0; j <= bagweight; j++) {
for(int i = 1; i < weight.size(); i++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
|
最终代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <vector>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
vector<int> weight(m,0);
vector<int> value(m,0);
for(int i=0;i<m;i++)
cin>>weight[i];
for(int i=0;i<m;i++)
cin>>value[i];
vector<vector<int>> dp(m,vector<int>(n+1,0));
for(int i=weight[0];i<=n;i++) dp[0][i]=value[0];
for(int i=1;i<m;i++){
for(int j=0;j<=n;j++){
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
}
}
cout<<dp[m-1][n]<<endl;
}
|
01背包理论基础（滚动数组）
二维dp降为一维dp
使用二维数组的时候，递推公式：;
可以发现如果把那一层拷贝到上，表达式完全可以是：;
与其把这一层拷贝到上，不如只用一个一维数组了，只用（一维数组，也可以理解是一个滚动数组）。
那么更改后结果为：
定义： dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
递推公式：
初始化： dp[0]=0,如果题目给的价值都是正整数那么非0下标都初始化为0
遍历顺序：
1
2
3
| for(int i = 0; i < weight.size(); i++)
for(int j = bagWeight; j >= weight[i]; j--)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
|
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
原因：倒序遍历是为了保证物品i只被放入一次，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
最终代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <vector>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
vector<int> weight(m,0);
vector<int> value(m,0);
for(int i=0;i<m;i++)
cin>>weight[i];
for(int i=0;i<m;i++)
cin>>value[i];
vector<int> dp(n+1,0);
for(int i=0;i<m;i++)
for(int j=n;j>=weight[i];j--)
dp[j]=max(dp[j], dp[j-weight[i]]+value[i]);
cout<<dp[n]<<endl;
}
|
一维二维对比：
完全背包理论基础
完全背包: 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包的核心代码
1
2
3
4
5
| for(int i = 0; i < weight.size(); i++) {
for(int j = bagWeight; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
|
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
完全背包核心代码
1
2
3
4
5
6
| for(int i = 0; i < weight.size(); i++) {
for(int j = weight[i]; j <= bagWeight ; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
|
而完全背包的物品是可以添加多次的，所以要从小到大去遍历。
还有使用一维或二维dp数组的遍历顺序问题
在01背包中，二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的。因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
52. 携带研究材料（第七期模拟笔试） (kamacoder.com)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
#include <vector>
using namespace std;
int func(vector<int> weight, vector<int> value, int bagsize) {
vector<int> dp(bagsize + 1, 0);
for (int i = 0; i < weight.size(); i++) {
for (int j = weight[i]; j <= bagsize; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[bagsize];
}
int main() {
int n, v;
cin >> n >> v;
vector<int> weight(n, 0);
vector<int> value(n, 0);
for (int i = 0; i < n; i++)
cin >> weight[i] >> value[i];
cout << func(weight, value, v) << endl;
return 0;
}
|
多重背包理论基础
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包与01背包相似，将Mi件物品铺开则可转换
56. 携带矿石资源（第八期模拟笔试） (kamacoder.com)
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<iostream>
#include<vector>
using namespace std;
int main() {
int C,N;
cin>>C>>N;
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> count(N,0);
for(int i=0;i<N;i++) cin>>weight[i];
for(int i=0;i<N;i++) cin>>value[i];
for(int i=0;i<N;i++) cin>>count[i];
vector<int> dp(C + 1, 0);
cout<<dp[C]<<endl;
}
|
将其转化成01背包，
方法一：先添加比较费时，C++中主要消耗在vector的动态底层扩容上。（其实这里也可以优化，先把 所有物品数量都计算好，一起申请vector的空间。
1
2
3
4
5
6
7
| for (int i = 0; i < n; i++) {
while (nums[i] > 1) {
weight.push_back(weight[i]);
value.push_back(value[i]);
nums[i]--;
}
}
|
方法二，在遍历时处理
1
2
3
| for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
|
故整体代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
#include<vector>
using namespace std;
int main() {
int C,N;
cin>>C>>N;
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> count(N,0);
for(int i=0;i<N;i++) cin>>weight[i];
for(int i=0;i<N;i++) cin>>value[i];
for(int i=0;i<N;i++) cin>>count[i];
vector<int> dp(C + 1, 0);
for(int i=0;i<N;i++){
for(int j=C;j>=weight[i];j--){
for(int k=1;k<=count[i]&&(j-k*weight[i])>=0;k++){
dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]);
}
}
}
cout<<dp[C]<<endl;
}
|
总结
问能否能装满背包（或者最多装多少）：，对应题目如下：
问装满背包有几种方法：，对应题目如下：
问背包装满最大价值： ，对应题目如下：
问装满背包所有物品的最小个数： ，对应题目如下：
