0/1背包问题(一道编程题)

0/1背包问题。

包重量max,有物件m1,m2,m3...n，任意取出物件加起来重量正好为包的容量，求装了哪些物件。

这个可能有解，可能无解，也可能多个解。

下面这个算法用递归来做，不过只能求出有解情况的一个解。

package example.algorithm;
public class Knap {/*** 0/1背包问题。all 为所有物件。max为包的容量。要求拿出的物件加起来正好是包的重量。* 这个算法只能算出一种结果。不能列出所有可能的组合。* @param args*/private int[] all;private int max;public boolean knapprocess(int m,int n) {boolean result;int x = m-all[n];if(x==0){result = true;System.out.println("包含"+all[n]);return result;}else if (x>0){if(n<=0) return false;//说明全加起来也不够if(knapprocess(x,n-1)){System.out.println("包含"+all[n]);return true;}else if (knapprocess(m,n-1)){return true;}elseresult = false;}else{if(n>0){if(knapprocess(m,n-1)){return true;}else{result = false;}}else{result = false;}}return result;}public static void main(String[] args) {// TODO Auto-generated method stubKnap knap = new Knap();knap.all = new int[]{1,2,3,4,5,6,7,8,9,10};knap.max = 21;System.out.println(knap.knapprocess(knap.max,knap.all.length-1));}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！