写在前面
背包问题, 采用动态规划的思想.
0-1背包
物品只能用一次
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每 件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
定义状态数组
dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量 为j的背包，价值总和最大是多少。
原始问题
class Solution {
public:
int BagMaxValue(vector<int>& value, vector<int>& weight, int maxWeight) {
// 滚动数组优化
int n = value.size();
vector<int> dp(maxWeight + 1);
for (int j{weight[0]}; j <= maxWeight; ++j)
if (weight[0] <= j) dp[j] = value[0];
cout << dp;
// for不可换序
for (int i{1}; i < n; ++i) { // object
for (int j{maxWeight}; j >= weight[i]; --j) // bag-weight
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
cout << dp;
}
return dp[maxWeight];
}
int BagMaxValue1(vector<int>& value, vector<int>& weight, int maxWeight) {
// 二维DP
int n = value.size();
vector<vector<int>> dp(n, vector<int>(maxWeight + 1));
for (int j{weight[0]}; j <= maxWeight; ++j)
if (weight[0] <= j) dp[0][j] = value[0];
cout << dp;
// for换序也可
for (int j{}; j <= maxWeight; ++j) // bag-weight
for (int i{1}; i < n; ++i) // object
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;
return dp[n - 1][maxWeight];
}
};
int main(int argc, char const* argv[]) {
Solution s;
vector<int> v{15, 20, 30}, w{1, 3, 4};
int mw = 4;
cout << s.BagMaxValue(v, w, mw) << endl;
return 0;
}
相关变形题
416. 分割等和子集 - 力扣（LeetCode）;(回溯会超时)
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
int n = nums.size();
if (total & 1 || n < 2) return false;
int target = total >> 1, dp[target + 1];
memset(dp, 0, sizeof(dp));
for (int i{}; i < n; ++i)
for (int j{target}; j >= nums[i]; --j)
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
return dp[target] == target;
}
};
1049. 最后一块石头的重量 II - 力扣（LeetCode）;
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size(),
sum = accumulate(stones.begin(), stones.end(), 0);
int target{sum >> 1}, dp[target + 1];
memset(dp, 0, sizeof(dp));
for (int i{}; i < n; ++i)
for (int j{target}; j >= stones[i]; --j)
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
return sum - (dp[target] << 1);
}
};
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum < target || (sum + target) & 1) return 0;
int m{(sum - target) >> 1}, dp[m + 1]; // 可能有负数
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i{}; i < nums.size(); ++i)
for (int j{m}; j >= nums[i]; --j) dp[j] += dp[j - nums[i]];
return dp[m];
}
};
474. 一和零 - 力扣（LeetCode）; (两个维度 m,n 的 0-1 背包)
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int dp[m + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (auto s : strs) {
int one{}, zero{};
for (auto c : s) c == '1' ? ++one : ++zero;
for (int i{m}; i >= zero; --i)
for (int j{n}; j >= one; --j)
dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
}
return dp[m][n];
}
};
完全背包
物品可以重复. 这时候需要考虑遍历顺序(先背包还是先物品)
先遍历背包, 此时就是排列, 因为对每一个遍历到的背包都要从头开始放物品
先遍历物品, 此时是组合, 物品每次只(在第一重循环中)被选择一次.
class Solution {
public:
int numSquares(int n) {
int dp[n + 1];
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i{1}; i * i <= n; ++i) // 物品:每一个平方数
for (int j{1}; j <= n; ++j) // 背包: 目标值 n
if (j >= i * i) dp[j] = min(dp[j], dp[j - i * i] + 1);
return dp[n];
}
};
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int dp[amount + 1];
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int c : coins)
for (int j{1}; j <= amount; ++j)
if (j >= c) dp[j] = min(dp[j], dp[j - c] + 1);
return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
}
};
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i{}; i < coins.size(); ++i)
for (int j{coins[i]}; j <= amount; ++j)
dp[j] += dp[j - coins[i]];
return dp[amount];
}
};
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
unsigned long long dp[target + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i{1}; i <= target; ++i) // 先遍历背包以得到排列
for (int num : nums)
if (i >= num) dp[i] += dp[i - num];
return dp[target];
}
};
记忆化搜索:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
int dp[n];
memset(dp, -1, sizeof(dp));
unordered_set<string> st(wordDict.begin(), wordDict.end());
function<bool(int)> f = [&](int x) {
if (x == n) return true;
if (~dp[x]) return dp[x] == 1; // 保证 function 函数对象的返回值为 bool
for (int i{x}; i < n; ++i) {
auto w = s.substr(x, i - x + 1);
if (st.count(w) && f(i + 1)) {
dp[x] = 1;
return true;
}
}
dp[x] = 0;
return false;
};
return f(0);
}
};
背包:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> st(wordDict.begin(), wordDict.end());
int n = s.size();
bool dp[n + 1];
memset(dp, 0, sizeof(dp));
dp[0] = true;
for (int i{1}; i <= n; ++i) // 背包, 长度 i
for (int j{}; j < i; ++j) // 物品
if (st.find(s.substr(j, i - j)) != st.end() && dp[j])
dp[i] = true; // 无后效性, 不能每次赋值
return dp[n];
}
};