0-1背包的各种算法解法

0-1背包问题 算法设计 各种解法 动态规划 贪心 回溯 分支限界

package test;
import java.util.*;
/**
 * 分支界限法解0-1背包问题。
 */
public class BBKnapsack {
	double c;// 背包重量
	int n; // 物品总数
	double[] w;// 物品重量数组
	double[] p;// 物品价值数组
	double cw; // 当前重量
	double cp; // 当前价值
	int[] bestx; // 最优解
	MaxHeap maxHeap = new MaxHeap（）;// 活节点优先队列

	// 计算节点所对应的节点的上界
	private double bound（int i） {
		double cleft = c - cw;
		double b = cp;

		// 以物品单位重量价值递减装填剩余容量
		while （i <= n && w[i] <= cleft） {
			cleft -= w[i];
			b += p[i];
			i++;
		}

		// 装填剩余容量装满背包
		if （i <= n） {
			b += p[i] / w[i] * cleft;
		}
		return b;
	}

	// 添加新的活节点到子集树和优先队列中
	private void addLiveNode（double upperProfit double pp double ww
			int level BBnode parent boolean leftChild） {
		BBnode b = new BBnode（parent leftChild）;
		HeapNode node = new HeapNode（b upperProfit pp ww level）;
		maxHeap.put（node）;
	}

	// 优先队列式分支界限法
	private double bbKnapsack（） {
		BBnode enode = null;
		int i = 1;
		double bestp = 0.0;
		double up = bound（1）;

		while （i != n + 1） {
			double wt = cw + w[i];

			// 检查当前扩展节点的左儿子节点
			if （wt <= c） {
				if （cp + p[i] > bestp） {
					bestp = cp + p[i];
				}
				addLiveNode（up cp + p[i] cw + w[i] i + 1 enode true）;
			}
			up = bound（i + 1）;

			// 检查当前扩展节点的右儿子节点
			if （up >= bestp） {
				addLiveNode（up cp cw i + 1 enode false）;
			}
			HeapNode node = maxHeap.removeMax（）;
			enode = node.liveNode;
			cw = node.weight;
			cp = node.profit;
			up = node.upperProfit;
			i = node.level;
		}

		// 构造当前最优解
		for （int j = n; j > 0; j--） {
			bestx[j] = （enode.leftChild） ? 1 : 0;
			enode = enode.parent;
		}
		return cp;
	}

	/**
* 将个物体依其单位重量价值从大到小排列，然后调用bbKnapsack完成对子集树优先队列式分支界
*限搜索。
	 * 
	 * @return 最优解
	 */
	public double knapsack（double[] pp double[] ww double cc int[] xx） {
		c = cc;
		n = pp.length;
		Element[] q = new Element[n];
		double ws = 0.0;
		double ps = 0.0;
		for （int i = 0; i < n; i++） {
			q[i] = new Element（i + 1 pp[i] / ww[i]）;
			ps += pp[i];
			ws += ww[i];
		}

		if （ws <= c） {
			for （int i = 1; i <= n; i++） {
				xx[i] = 1;
			}
			return ps;
		}

		// 依单位重量价值排序
		Arrays.sort（q new ElemComparator（））;
		p = new double[n + 1];
		w = new double[n + 1];
		for （int i = 1; i <= n; i++） {
			p[i] = pp[q[i - 1].id - 1];
			w[i] = ww[q[i - 1].id - 1];
		}
		cw = 0.0;
		cp = 0.0;
		bestx = new int[n + 1];
		maxHeap = new MaxHeap（）;

		// 调用bbKnapsack求问题的最优解
		double maxp = bbKnapsack（）;
		for （int i = 1; i <= n; i++） {
			xx[q[i - 1].id - 1] = bestx[i];
		}
		return maxp;
	}

	public static void main（String arg[]） {
		double c = 10;
		int n=5;
		double[] v= {63546};
		double[] w={22654};
		int[] xx=new int[5];
		double bestP=0.0;
		System.out.println（“*****分支限界法*****“）;
        System.out.println（“物品个数：n=5“）;
        System.out.println（“背包容量：c=10“）;
        System.out.println（“物品重量数组：w= {22654}“）;
        System.out.println（“物品价值数组：v= {63546}“）;
		BB

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2011-12-13 10:30  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\
     文件        5484  2011-11-29 21:20  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\BBKnapsack（分支限界）.java
     文件        2619  2011-11-30 12:16  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\BTKnapsack（回溯）.java
     文件        2165  2011-11-30 12:17  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\Knapsack（动态规划）.java
     文件        2641  2011-11-30 12:17  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\Knapsack_tx（贪心）.java
     文件      163328  2011-11-29 21:20  0-1背包问题动态规划，贪心，回溯，分支限界算法的设计与实现\算法分析1.doc