通过递归解决0-1背包代码,Java代码库,德仔网

代码语言

代码分类

【Java】通过递归解决0-1背包

作者:步山 / 发布于2014/11/10/ 453

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}


	* @author Sun Kui
	*/
	public class Knapsack {
	 public static void main(final String... args) {
	 int[] arr = new int[5];
	 arr[0] = 11;
	 arr[1] = 8;
	 arr[2] = 7;
	 arr[3] = 5;
	 arr[4] = 3;
	 Knapsack k = new Knapsack();
	 System.out.println(k.knapsack(arr, 0, 20, 20));
	 }

	 /**
	 *@param arr all of items in knapsack
	 *@param start the start item to be put into the knapsack
	 *@param left the remaining capacity of knapsack
	 *@param sum capacity of knapsack
	 */
	 public boolean knapsack(int[] arr, int start, int left, int sum) {

	 if (arr.length == 0) {
	 return false;
	 }

	 // start from the next item in original array
	 if (start == arr.length) {
	 int[] tempArr = new int[arr.length - 1];
	 for (int i = 0; i < tempArr.length; i++) {
	 tempArr[i] = arr[i + 1];
	 }
	 return knapsack(tempArr, 0, sum, sum);
	 } else if (arr[start] > left) {
	 return knapsack(arr, start + 1, left, sum);
	 } else if (arr[start] == left) {
	 for (int i = 0; i < start + 1; i++) {
	 // print the answer out
	 System.out.print(arr[i] + "\t");
	 }
	 System.out.println();
	 return true;
	 } else {
	 return knapsack(arr, start + 1, left - arr[start], sum);
	 }
	 }
	}

试试其它关键字

　递归　

同语言下

可能有用的

步山贡献的其它代码(75)