區分一維和二維
一維和二維的區分，并不是體現在陣列的維數上！！！
而是體現在概念上：
二維指的是下標體現了兩個方面：
- 物品的選擇
- 關于背包容量
一維指下標僅代表：
- 背包的容量
一維和二維的代碼
二維
dp[i][j]表示 從下標為[0-i]的物品里任意取，放進容量為j的背包，背包價值總和最大是dp[i][j]
// weight陣列的大小 就是物品個數
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]);
}
}
一維
dp[j]表示 背包容量為j 所能放的最大價值為dp[j]
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[i][j]只與上一層左上角部分狀態有關系，不能破壞上一層狀態；
一維時，當上一層狀態壓縮到這一層，也就是指dp[0-j]這一部分其實是上一層的狀態不可以破壞，那么只能從后向前遍歷，
正序會導致重復放入同一件物品
舉一個例子：物品0的重量weight[0] = 1，價值value[0] = 5
如果正序遍歷
dp[1] = dp[1 - weight[0]] + value[0] = 5
dp[2] = dp[2 - weight[0]] + value[0] = 10
此時dp[2]就已經是10了，意味著物品0被放入了兩次，因此不能正序遍歷
- 既然會重復放入，由此可以引申出
完全背包的寫法
// 先遍歷物品，再遍歷背包
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[j] = max(dp[j], dp[j - weight[i]] + value[i]);中 先背包容量使得沒有前一層狀態
例題：LC474 一和零
題目
https://leetcode.cn/problems/ones-and-zeroes/
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
示例 1：
輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個 0 和 3 個 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 ，
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} ，{"111001"} 不滿足題意，因為它含 4 個 1 ，大于 n 的值 3 ，示例 2：
輸入：strs = ["10", "0", "1"], m = 1, n = 1
輸出：2
解釋：最大的子集是 {"0", "1"} ，所以答案是 2 ，
Constraints:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits '0' and '1'.
- 1 <= m, n <= 100
MY
我的錯誤在于沒有正確理解背包的優化所在，
思路
這里背包的要求有兩個要求，這是一個二維容量的背包：m個0，n個1
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默認初始化0
for (string str : strs) { // 遍歷物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
- 參考《代碼隨想錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540197.html
標籤：其他