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?			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