本文主要是介绍类多重背包问题例题 Lintcode668 Ones and Zeroes(一和零),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
动态规划组成部分一:确定状态
动态规划组成部分二:转移方程
动态规划组成部分三:初始条件和边界情况
动态规划组成部分四:计算顺序
Java代码实现
public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;int[] zero = new int[len];int[] one = new int[len];char[] chars;for (int i = 0; i < len; i++) {chars = strs[i].toCharArray();for (int j = 0; j < chars.length; j++)if (chars[j] == '0')zero[i]++;elseone[i]++;}int[][][] f = new int[len + 1][m + 1][n + 1];for (int i = 1; i <= len; i++)for (int j = 0; j <= m; j++)for (int k = 0; k <= n; k++) {f[i][j][k] = f[i - 1][j][k];if ((j >= zero[i-1]) && (k >= one[i-1]))f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - zero[i-1]][k - one[i-1]] + 1);}return f[len][m][n];}
这篇关于类多重背包问题例题 Lintcode668 Ones and Zeroes(一和零)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!