01背包理论基础
- 问题定义：有n件物品和一个能装重量为w的背包，第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包获得的总价值最大。
- dp数组含义：dp[i][j] 表示从下标为 [0,i] 的物品中选，放进容量为j的背包中，能得到的最大价值总和。
- 确定递推公式：在推导 dp[i][j] 时有两个方面：一是不放物品i，因为不放i物品，所以
dp[i][j] = dp[i - 1][j]，是只放前 i-1 个物品时的最大值；二是放物品i，dp[i][j] = dp[i - 1][j - weight[i]] + value[i]。当背包容量小于i号物品重量时赋值第一方面的值，否则赋值为两种情况的最大值。 - 确定初始化：dp[i][0] 由于背包容量为0，根本放不进物品，所以初始化为0。dp[0][j] 只放0号物品，当 j >= weight[0] 时有值value[0]，其他情况为0。
- 遍历顺序：这是重点，要决定当前的状态，必须由其左上角的状态决定。先遍历物品还是先背包容量都是可以的。
#include <bits/stdc++.h>
using namespace std;
int n, bagweight;
void solve() {
vector<int> weight(n, 0);
vector<int> value(n, 0);
for(int i = 0; i < n; i++) {
cin >> weight[i];
}
for(int i = 0; i < n; i++) {
cin >> value[i];
}
vector<vector<int>> dp(n, vector<int>(bagweight + 1, 0));
for(int i = weight[0]; i <= bagweight; i++) { // 初始化
dp[0][i] = value[0];
}
for(int i = 1; i < n; i++) {
for(int j = 1; 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]);
}
}
cout << dp[n - 1][bagweight] << endl;
}
int main() {
while(cin >> n >> bagweight) {
solve();
}
return 0;
}
滚动数组空间优化
我们观察二维数组的递推式，可以发现 dp[i][j] 只与 i - 1 那一层的状态有关。因此可以用一个一维数组来表示状态。
- dp[j] 表示容量为 j 的背包能获得的最大价值总和。
- 因为在当前遍历过程中 dp 中存储的就是上一层的状态，因此状态递推式为
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) - 初始化：下标0位置一定初始化为0，其他位置为了递推式中的取最大值服务，也初始化为0即可。
- 遍历顺序：背包容量的遍历需要从大到小，倒序遍历是为了保证物品i只被放入一次。当前遍历中未处理的部分都是i-1那一层的值，因此只有倒序遍历才能保证用到的状态没用过物品i。另一方面，我们更新状态需要知道当前位置左侧的i-1状态 (j-weight[i])，正序遍历就让左侧的状态变成当前层的。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, bagweight;
while(cin >> n >> bagweight) {
vector<int> weight(n, 0);
vector<int> value(n, 0);
for(int i = 0; i < n; i++) {
cin >> weight[i];
}
for(int i = 0; i < n; i++) {
cin >> value[i];
}
vector<int> dp(bagweight + 1, 0);
for(int i = 0; i < n; i++) {
for(int j = bagweight; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagweight] << endl;
}
return 0;
}
分割等和子集
其实用回溯可解，但是会超时。因为每一个元素只能用一次，考虑01背包试一下。
背包的大小为 sum / 2，每一个元素看做物品，其重量为元素值，价值也为元素值。问题就转换成在sum / 2的背包中放入元素，让背包尽可能的满，由于重量等于价值，就变成让价值总和尽量大，最终查看最大值是否与sum / 2相等，就能判断能不能分割。
class Solution{
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int num : nums) {
sum += num;
}
if(sum % 2) return false; // 和为奇数，不可能分成相等的两份
int target = sum / 2; // 背包大小
vector<int> dp(target + 1, 0);
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target;
}
};
