背包问题_完美解法

package qinglin.learn.arithmetic;

public class SackPro_01
{
	public static void main(String[] args)
	{
		int[] src = { 2, 4, 5, 7, 10 };
		select(18, src, 0, new int[src.length]);
	}
	/**  
	 * @param total 总数  
	 * @param src 源数据数组  
	 * @param offset 源数组的起始位置  
	 * @param bag 背包，装选中的数据  
	 */
	private static void select(int total, int[] src, int offset, int[] bag)
	{
		if (total == 0)
		{ //背包要求增加的重量为0,则直接打印背包  ,即递归结束条件 
			print(bag);
			return;
		}
		//从起始值开始寻找第一个小于要求增加重量的数值   
		while (offset < src.length && total < src[offset])
			offset++;
		if (offset >= src.length)
			return; //当没有源数据可以选择，则退出   
		//将问题化简为在剩下的源数据中，两个找到重量的问题   
		select(total, src, offset + 1, bag.clone()); //背包中含有offset位置的   
		select(total - src[offset], src, offset + 1, put(bag, src[offset]));//背包中不含有offset位置的   
	}

	private static int[] put(int[] bag, int n)
	{ //将数字放入背包中   
		int pos = -1;
		while (bag[++pos] > 0)
			; //找到背包中第一个数字为0的位置   
		bag[pos] = n;
		return bag;
	}

	private static void print(int[] bag)
	{ //打印背包中的数字   
		System.out.print("bag: ");
		for (int n : bag)
		{
			if (n == 0)
				break;
			System.out.print(n + " ");
		}
		System.out.println();
	}
}
/*using namespace std;

 class Knapsack
 {
	 public:
	 Knapsack(double *pp,double *ww,int nn,double cc)
	 {
		 p = pp;
		 w = ww;
		 n = nn;
		 c = cc;
		 cw = 0;
		 cp = 0;
		 bestp = 0;
		 x = new int[n];
		 cx = new int[n];
	 }
	 
	 void knapsack()
	 {
	 	 backtrack(0);
	 }
	 
	 void backtrack(int i)
	 {//回溯法
		 if(i > n)
		 {
			 if(cp > bestp)
			 {
				 bestp = cp;
				 for(int i = 0; i < n; i++)   
				 x[i] = cx[i];   
			 }
			 return;   
		 }
		 if(cw + w[i] <= c)
		 {//搜索右子树   
			 cw += w[i];   
			 cp += p[i];   
			 cx[i] = 1;   
			 backtrack(i+1);   
			 cw -= w[i];   
			 cp -= p[i];   
		 }
		 cx[i] = 0;   
		 backtrack(i+1);//搜索左子树   
	 }   
	 
	 void printResult()
	 {   
		 cout << "可以装入的最大价值为:" << bestp << endl;   
		 cout << "装入的物品依次为:";   
		 for(int i = 0; i < n; i++)
		 {   
			 if(x[i] == 1)
			 cout << i+1 << " ";
		 }   
		 cout << endl;
	 }   	 
	 private:   
	 double *p,*w;   
	 int n;   
	 double c;   
	 double bestp,cp,cw;//最大价值，当前价值，当前重量   
	 int *x,*cx;   
};

 int main()
 {
	 double p[4] = {9,10,7,4},w[4] = {3,5,2,1};
	 Knapsack ks = Knapsack(p,w,4,7);
	 ks.knapsack(); 
	 ks.printResult();   
	 return 0;   
 }
*/