背包问题
0-1 背包问题
Question
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays $values[0..n-1]$ and $weights[0..n-1]$ which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of $values[0..n-1]$ such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
- From: GeekforGeeks
Analyze
每件物品只有一个，那么考虑最后一个物品 $i$ ，一共就放或者不放两种状态选择。如果不放第 $i$ 件物品，那么问题转化为 前 $i-1$ 件物品放入到容量为 $j$ 的背包中, 即为 $M[i, j] = M[i-1, j]$。如果放第 $i$ 件物品，那么就是 前 $i-1$ 件物品放到容量为 $j-W_i$ 的背包中的 $value$ 加上把第 $i$ 件物品放入背包中的价值，即为 $M[i, j] = M[i-1, j - weights_i + values_i]$.
此外，这个问题问得是得到的结果尽可能大，并不要求背包正好装满，初始化的时候都是 0。 如果要求恰好装满背包，那么除了 $M[0, 0]$ 初始化为 0 之外，其他都初始化为负无穷大。这样就可以保证最终的到的结果是一种恰好装满背包的最优解。
Solution
int knapsack(int W, vector<int> weights, vector<int> values) {
int n = weights.size();
vector<vector<int>> M(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (weights[i - 1] <= j) {
M[i][j] = max(values[i-1] + M[i-1][j - weights[i - 1]], M[i-1][j]);
}
else {
M[i][j] = M[i-1][j];
}
}
}
return M.back().back();
}
Space Optimization
如果对以上代码填表，可以更直观的显示出当前状态只跟上一行的状态有关。所以空间复杂度可以优化到 $O(n)$.
int knapsack(int W, vector<int> weights, vector<int> values) {
int n = weights.size();
vector<int> M(W + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = W; j >= weights[i]; j--) {
M[j] = max(M[j], values[i] + M[j - weights[i]]);
}
}
return M.back();
}
Print all items
int knapsack(int W, vector<int> weights, vector<int> values) {
int n = weights.size();
vector<vector<int>> M(n + 1, vector<int>(W + 1, 0));
//M[0][0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (weights[i - 1] <= j) {
M[i][j] = max(values[i-1] + M[i-1][j - weights[i - 1]], M[i-1][j]);
}
else {
M[i][j] = M[i-1][j];
}
}
}
int res = M.back().back();
for (int i = n; i > 0 && res > 0; i--) {
if (res == M[i-1][W])
continue;
else {
cout << weights[i-1] << " ";
}
res -= values[i-1];
W = W - weights[i-1];
}
return res;
}
House Robber
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
if (nums.size() <= 2) {
return max(nums[0], nums.back());
}
vector<int> M(nums.size(), 0);
M[0] = nums[0];
M[1] = max(nums[0], nums[1]);
for (int i = 2; i < M.size(); i++) {
M[i] = max(M[i - 2] + nums[i], M[i - 1]);
}
return M.back();
}
};
完全背包问题
由于每个物品的数量变成了无限，那么从0-1背包问题转变过来，从取或者不取两种状态转换到了取0个，取1个到最多取 $k = \frac{Capacity}{weights[i]}$ 个。
Example - Coin Change II
//O(n*amount*amount)
//O(mn)
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
/*
M[i][j] => the number of combinations to make up amount j with the first i types of coins
M[i][j] = M[i-1][j], use coins[i-1] 0 times
+ M[i-1][j - coins[i-1]] use coins[i-1] 1 time
+ M[i-1][j- coins[i-1] * 2] use coins[i-1] 2 times
+ M[i-1][j- coins[i-1] * 3] use coins[i-1] 3 times
...
*/
vector<vector<int>> M(n + 1, vector<int>(amount + 1, 0));
M[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
M[i][j] = 0;
for (int k = 0; k * coins[i - 1] <= j; k++) {
M[i][j] += M[i - 1][j - k * coins[i - 1]];
}
}
}
return M.back().back();
}
};
Time Optimization
//O(n*amount)
//O(mn)
class Solution {
public:
/*
1.
f[i][j] = f[i-1][j]
+ f[i-1][j - coins[i-1]]
+ f[i-1][j - coins[i-1] * 2]
+ f[i-1][j - coins[i-1] * 3]
...
2.
f[i][j - coins[i-1]]
= f[i-1][j-coins[i-1]]
+ f[i-1][j-coins[i-1] * 2]
+ f[i-1][j-coins[i-1] * 3]
...
3.
f[i][j] = f[i-1][j]
+ f[i][j - coins[i-1]]
*/
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> M(n + 1, vector<int>(amount + 1, 0));
M[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
M[i][j] = M[i-1][j] + (coins[i-1] <= j? M[i][j - coins[i - 1]] : 0);
}
}
return M.back().back();
}
};
Space Optimization
//O(n*amount)
//O(amount)
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> M(amount + 1, 0);
M[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
if (coins[i-1] <= j) {
M[j] += M[j - coins[i -1]];
}
}
}
return M.back();
}
};
Minimum Number of Refueling Stops
Recursive - LTE
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
if (stations.empty()) return startFuel >= target? 0 : -1;
stations.insert(stations.begin(), {0, startFuel});
int res = INT_MAX;
helper(0, res, 0, startFuel, stations, target);
return res == INT_MAX? -1 : res;
}
void helper(int level, int & res, int num, int remain, const vector<vector<int>> & stations, int target) {
if (remain < 0) {
return;
}
if (level == stations.size()) {
res = min(res, num);
return;
}
int cost = (level == stations.size() - 1)? target - stations[level][0] : stations[level + 1][0] - stations[level][0];
int refuel = (level == stations.size() - 1)? 0 : stations[level+1][1];
if (cost <= remain) {
helper(level + 1, res, num, remain - cost, stations, target);
helper(level + 1, res, num + 1, remain - cost + refuel, stations, target);
}
}
};
DP knapsack solution
class Solution {
public:
// dp[i][j]: pick j stops to refill from [0, i] stops, how far away can we go
// dp[i][j] = max {dp[i-1][j] >= stations[i-1][0] ? dp[i-1][j] : 0
// = dp[i-1][j-1] >= stations[i-1][0] ? dp[i-1][j-1] + stations[i-1][1] : 0 }
//
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
int n = stations.size();
vector<vector<long>> M(n+1, vector<long>(n+1, 0));
M[0][0] = startFuel;
for (int i = 1; i <= n; i++) {
if (startFuel >= stations[i-1][0])
M[i][0] = startFuel;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (M[i-1][j] >= stations[i-1][0]) {
M[i][j] = M[i-1][j];
}
if (M[i-1][j-1] >= stations[i-1][0]) {
M[i][j] = max(M[i][j], M[i-1][j-1] + stations[i-1][1]);
}
}
}
for (int t = 0; t <= n; ++t)
if (M[n][t] >= target) return t;
return -1;
}
};
TODO: space optimization