文档网

递归 背包问题

package com.neil.algorithms;

/**

* 递归求01背包问题

*

* @author neil

* @date 下午12:01:27

* @filename BagProblem.java

*/

public class BagProblem {

public static void main(String[] args) {

int[] array = new int[] { 1, 2, 3, 4, 2, 4, 11, 23, 43, 12, 6 };

knap(12, array.length - 1, array);

}

public static boolean knap(int m, int n, int[] array) {

// 如果放入的质量等于包剩余的容量

if (m == array[n]) {

System.out.print(array[n] + " ");

return true;

// 如果放入的质量小于包剩余的容量

} else if (m > array[n]) {

// 如果还有剩余物品

// 如果放入这个之后,knap(m-array[n],n-1,array)有解,那么就放入这个

if (n > 0) {

if (knap(m - array[n], n - 1, array)) { System.out.print(array[n] + " "); return true;

// 如果放入这个之

后,knap(m-array[n],n-1,array)无解,那么就考虑knap(m, n - 1,array)

} else {

return knap(m, n - 1, array);

相关文档
热门文档
你可能喜欢
  • 动态规划1背包问题
  • 梯形动点问题
  • 回溯法-1背包问题
  • qq空间问题
  • 赛马问题
  • 背包问题贪婪算法visualc
  • 动态规划算法-1背包问题
评论