Leetcode|01背包|474. 一和零（二维01背包）

SL_World

发布于 2021-09-18 16:40:32

7610

发布于 2021-09-18 16:40:32

文章被收录于专栏：X

1 动态规划（二维01背包）

【dp[i][j]数组含义】：容量0的个数最多为i且1的个数最多为j的情况下，两个维度容量的背包下最多的子集数【状态转移方程】：dp[i][j] = max(dp[i][j], dp[i - cont0][j - cont1] + 1)

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int size = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int k = 0; k < size; k++) {         // 遍历物品
            int cont0 = 0, cont1 = 0;
            for (auto& ch : strs[k]) {
                if (ch == '0') cont0++;
                else cont1++;
            }
            for (int i = m; i >= cont0; i--)     // 遍历容量（倒序）
                for (int j = n; j >= cont1; j--) 
                    dp[i][j] = max(dp[i][j], dp[i - cont0][j - cont1] + 1);      
        }           
        return dp[m][n];
    }
};