宿州网站公司,站酷网app,兰州市网站,wordpress瀑布流分页学习要点
给定背包容量#xff0c;装满背包最多有多少个物品深入理解01背包深入理解动态规划
题目链接 474. 一和零 - 力扣#xff08;LeetCode#xff09;
题目描述 解法:01背包
class Solution {
public:int findMaxForm(vectorstring strs, int m, int …学习要点
给定背包容量装满背包最多有多少个物品深入理解01背包深入理解动态规划
题目链接 474. 一和零 - 力扣LeetCode
题目描述 解法:01背包
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {// 求的是最大子集个数int size strs.size();vectorvectorvectorint dp(size,vectorvectorint(m1,vectorint(n1)));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;im;i){for(int j 0;jn;j){if(i a j b){dp[0][i][j] 1;}}}for(int i 1;isize;i){for(int j 0;jm;j){for(int k 0;kn;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 k0){dp[i][j][k] 0;}else if(j a || k b){dp[i][j][k] dp[i-1][j][k];}else if(ja kb){dp[i][j][k] max(dp[i-1][j][k],dp[i-1][j-a][k-b] 1);}}}}return dp[size -1][m][n];}
};
