學習要點

1. 給定背包容量，裝滿背包最多有多少個物品
2. 深入理解01背包
3. 深入理解動態規劃

題目鏈接

????????474. 一和零 - 力扣（LeetCode）

題目描述

解法:01背包

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 求的是最大子集個數int size =  strs.size();vector<vector<vector<int>>> dp(size,vector<vector<int>>(m+1,vector<int>(n+1)));int a = count_if(strs[0].begin(),strs[0].end(),[](char ch){return ch == '0';});int b = strs[0].size() - a;// cout << a << ' ' << b << endl;for(int i = 0;i<=m;i++){for(int j = 0;j<=n;j++){if(i >= a && j >= b){dp[0][i][j] = 1;}}}for(int i = 1;i<size;i++){for(int j = 0;j<=m;j++){for(int k = 0;k<=n;k++){int a = count_if(strs[i].begin(),strs[i].end(),[]( char ch){return ch == '0';});int b = strs[i].size() - a;// cout << a << ' ' << b << endl;if( j == 0 && k==0){dp[i][j][k] =0;}else if(j < a || k < b){dp[i][j][k] = dp[i-1][j][k];}else if(j>=a && k>=b){dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-a][k-b] + 1);}}}}return dp[size -1][m][n];}
};