題目

https://leetcode.com/problems/ones-and-zeroes/

題解

這是一個(gè)雙約束的背包問(wèn)題。此題需要的前置知識(shí)，可以參考我之前的博客：算法設(shè)計(jì)與分析 0-1背包問(wèn)題 動(dòng)態(tài)規(guī)劃解法【超詳細(xì)】

針對(duì)本題，思路如下：

在實(shí)現(xiàn)上，為了避免 i-1 的越界判斷，將整個(gè)數(shù)組的 i=0 位置空出來(lái)，顯得更整潔一些。

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個(gè)物品(序號(hào)從1開(kāi)始)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];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 474. Ones and Zeroes | 474. 一和零（双约束背包问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。