leetcode 474. Ones and Zeroes | 474. 一和零（双约束背包问题）

痛定思痛。 2022-09-09 12:51 12阅读 0赞

## 题目 ##

[https://leetcode.com/problems/ones-and-zeroes/][https_leetcode.com_problems_ones-and-zeroes]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

这是一个双约束的背包问题。此题需要的前置知识，可以参考我之前的博客：[算法设计与分析 0-1背包问题 动态规划解法【超详细】][0-1_]

针对本题，思路如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
在实现上，为了避免 i-1 的越界判断，将整个数组的 i=0 位置空出来，显得更整洁一些。

class Solution { 
        public int findMaxForm(String[] strs, int m, int n) { 
            int L = strs.length;
            int[][] weight = new int[L + 1][2];
            for (int i = 0; i < L; i++) { 
                int z = 0;
                int o = 0;
                for (int j = 0; j < strs[i].length(); j++) { 
                    if (strs[i].charAt(j) == '0') { 
                        z++;
                    } else { 
                        o++;
                    }
                }
                weight[i + 1][0] = z;
                weight[i + 1][1] = o;
            }
            int[][][] dp = new int[L + 1][m + 1][n + 1];
            for (int i = 1; i <= L; i++) {  // 第i个物品(序号从1开始)
                for (int mFree = 0; mFree <= m; mFree++) {  // 背包剩余x容量
                    for (int nFree = 0; nFree <= n; nFree++) {  // 背包剩余y容量
                        if (weight[i][0] > mFree || weight[i][1] > nFree) { 
                            dp[i][mFree][nFree] = dp[i - 1][mFree][nFree];
                        } else { 
                            dp[i][mFree][nFree] = Math.max(dp[i - 1][mFree - weight[i][0]][nFree - weight[i][1]] + 1, dp[i - 1][mFree][nFree]);
                        }
                    }
                }
            }
            return dp[L][m][n];
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_ones-and-zeroes]: https://leetcode.com/problems/ones-and-zeroes/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/50d191bd87b140c1a69eaf7214fb9ef1.png
[0-1_]: https://blog.csdn.net/sinat_42483341/article/details/89456491
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/e316311d428342d89371e776a83a859a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/232036f9e29c4c6abeb8b86c26ea720e.png