背包问题算法的JAVA实现
问题描述：设U = {u1,u2,u3,......ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.
定义每个物品都具有两个属性weight和value.
我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.
一句话，让你的有限背包，装上最终总价值最高的物品。
注意，代码里面我加上了打印语句，可以用来查看算法的过程
<div class="highlighter">
[*]import java.util.Arrays;
[*]<span />
[*]<span />/**
[*] * 背包问题
[*] * @author 赵学庆 java2000.net
[*] *
[*] */<span />
[*]public class T {
[*] /**
[*] * @param value 价值
[*] * @param weight 重量
[*] * @param capicity 背包容量
[*] * @param m 表示只有w,w...w这些物品时,背包容量为j时的最大价值
[*] */<span />
[*] public static void knapsack(int[] value, int[] weight, int capicity, int[][] m) {
[*] // 数量<span />
[*] int n = value.length - 1;
[*] // 最后一个重量-1和容量的更小的一个<span />
[*] int jMax = Math.min(weight - 1, capicity);
[*] // 将最后一个数组的前部分清空。<span />
[*] for (int j = 0; j <= jMax; j++)
[*] m = 0; // 当w>j 有 m=0<span />
[*] showArray(m);
[*] // 后半部分设置为此物品的价值<span />
[*] // m 表示只有w物品，背包的容量为j时的最大价值<span />
[*] for (int j = weight; j <= capicity; j++)
[*] m = value; // 当w<=j 有m=v<span />
[*] showArray(m);
[*] // 递规调用求出m[][]其它值，直到求出m<span />
[*] for (int i = n - 1; i >= 1; i--) {
[*] jMax = Math.min(weight - 1, capicity);
[*] System.out.println(jMax);
[*] for (int k = 0; k <= jMax; k++)
[*] m = m;
[*] showArray(m);
[*] for (int h = weight; h <= capicity; h++) {
[*] System.out.println(m+" / "+ m]+" + " +value+"("+h+","+weight+","+value+")");
[*] m = Math.max(m, m] + value);
[*] }
[*] showArray(m);
[*] }
[*] m = m;
[*] if (capicity >= weight)
[*] m = Math.max(m, m] + value);
[*] System.out.println("bestw =" + m);
[*] }
[*]<span />
[*] public static void showArray(int[][] m) {
[*] for (int[] a : m) {
[*] System.out.println(Arrays.toString(a));
[*] }
[*] System.out.println("-------------------------------------------");
[*] }
[*]<span />
[*] public static void traceback(int[][] m, int[] w, int c, int[] x) {// 根据最优值求出最优解<span />
[*] int n = w.length - 1;
[*] for (int i = 0; i < n; i++)
[*] if (m == m)
[*] x = 0;
[*] else {
[*] x = 1;
[*] c -= w;
[*] }
[*] x = (m > 0) ? 1 : 0;
[*] }
[*]<span />
[*] public static void main(String[] args) {
[*] // 测试<span />
[*] int[] ww = { 8,5,4,3 };
[*] int[] vv = { 10,7,5,4 };
[*] int[][] mm = new int;
[*] knapsack(vv, ww, 12, mm);
[*] int[] xx = new int;
[*] traceback(mm, ww, 12, xx);
[*] for (int i = 0; i < xx.length; i++)
[*] System.out.println(xx);
[*] }
[*]}
页:
[1]