2023.8.15

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1, vector<int>(n+1,0));//遍歷物品for(string str : strs){int num_0 = 0;int num_1 = 0;for(char c : str){if(c == '0') num_0++;else num_1++;}//遍歷二維背包for(int i=m; i>=num_0; i--){for(int j=n; j>=num_1; j--){dp[i][j] = max(dp[i][j] , 1 + dp[i-num_0][j-num_1]);}}}return dp[m][n];}
};

? ? ? ? 依舊是0-1背包問題的應用。?本題不易看出是0-1背包問題，因為本題的背包有兩個：m和n。因此需要定義一個二維的dp數組。數組strs中的一個個字符串就是我們的物品。dp[i][j]的含義為：兩背包大小分別為i和j時，所能裝的最多物品。

? ? ? ??在遍歷物品（即字符串數組）時，需要先將每個物品（字符串）的0和1個數統計起來。然后分別遍歷兩個背包。每次更新dp數組時，可以選擇取當前物品或者不取當前物品。 不取當前物品：dp[i][j] = dp[i][j]；? 取當前物品：dp[i][j] = 1 + dp[i-num_0][j-num_1];? ?擇其最大的。

? ? ? ? 代碼如下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1, vector<int>(n+1,0));//遍歷物品for(string str : strs){int num_0 = 0;int num_1 = 0;for(char c : str){if(c == '0') num_0++;else num_1++;}//遍歷二維背包for(int i=m; i>=num_0; i--){for(int j=n; j>=num_1; j--){dp[i][j] = max(dp[i][j] , 1 + dp[i-num_0][j-num_1]);}}}return dp[m][n];}
};

? ? ? ? 至此，做了四道0-1背包應用的相關題目，總結一下：

分割等和子集：是求：給定背包容量，能否裝滿這個背包。

最后一塊石頭的重量II：是求：給定背包容量，盡可能裝，最多能裝多少。

目標和：是求：給定背包容量，裝滿背包有多少種方法。

本題：是求：給定背包容量，裝滿背包最多有多少個物品。