输入：第一行一个整数，为背包的容量M；第二行一个整数，为物品的种数Ｎ；第三行Ｎ个整数为各物品的重量；第四行Ｎ个整数分别为Ｎ个物品的价值

   输出：第一行为最大总价值；第二行为装入的各物品的重量（未装的物品用０）；第三行为装入的各物品的价值（未装的物品用０）

输入样例：
 50
 3
 10 20 30
 60 100 120
输出样例：
 220
 0 20 30
 0 100 120

解题思路：

对于每种可能的情况，进行判断，看是否是最优解；即对于每件物品，可以选择放（背包容量限制内），或是不放（不放的情况分别是当前背包放不下了，和如果这个不放，后面的可能使得value更大。）。然后对下一个物品进行判断，

解空间：

bag:array[1..maxn]of 0..1;

其中，bag[k]=1表示第k个物品要取

           0表示第k个物品不取

（ K 表示第K个物品；N表示物品的个数）

约束条件：

背包足以放下当前物品；

状态树：

Best:=0;   表示最大价值
当一组解产生后，得到当前总价值count，
if count>best then best:=count
利用这种方法记录最优解！如果还要记录最优时的物品取法应：
if count>best then begin
    best:=count;
    for i:=1 to n do y[i]:=bag[i];

结束条件：

所有的可用的解法都已经搜索完毕，即K>=N时；

求最优解步骤：

对于每一种可能的解法，都与当前最优解比较，进行更新。

即：在K>=N的时候将当前的值与最优解比较，即current_value与best比较。进行更新；

注意：

回溯过程中注意状态的回复。

当然，如果仅仅是这样的话，很容易实现，但是耗时很大。原因是进行了很多不必要的搜索，那么心在就是要来剪枝了。

上界函数：当前值+剩余的物品的值<=当前最优解best

当前值指的是第k 层之前的值，剩余物品的值指的是不包括当前物品，剩余的值

if(curp+r>best)
{
	plag[k]=0;
	fun(k+1);
}

       即 当这个物品不放置的时候，即使后面的都能放进去，得到的值也小于最优值的时候，以此节点后的子树就军事不可行解。可以不予判断（即舍弃这个子树）。

# include
# include
# include

# define M 1000

int w[M+100],p[M+100];
char plag[M+100],bag[+200]; 	//标记数组 
int r,best,curw,curp;			//剩余值，最优值，当前重量，当前值 
int n,m;

int fun(int k)
{
	int i;
	if(k>=n)
	{
		if(curp>best)			//更新操作 
		{
			for(i=0;ibest)			// 剪状态树枝 
		{
			plag[k]=0;
			fun(k+1);
		}
		r+=p[k];
	}
	return 0; 
}

int main(){
	
	int i;
	while(~scanf("%d",&m))
	{
		scanf("%d",&n);
		for(i=0;i 
  
 
 装载问题，与此类似。 
  
 
 
  
 
 
  
装载问题
 
  
 
    
   
 
  
 
  
 
    
   
 
  
 
  
 
   
 
  
 
  
 
  
 
 
  
 
 
  
 
 
  
 
   •解空间：子集树 
  
 
  
 
   •可行性约束函数(选择当前元素)： 
  
 
  
 
   •上界函数(不选择当前元素)： 
  
 
  
 
  
当前载重量cw+剩余集装箱的重量r£当前最优载重量bestw
 
  
 
 
  
 voidbacktrack(inti)
 
  
    {// 搜索第i层结点
 
  
       if (i > n) // 到达叶结点
 
  
       更新最优解bestx,bestw;return;
 
  
       r -= w[i];
 
  
       if (cw + w[i] <= c) {// 搜索左子树
 
  
          x[i] = 1;
 
  
          cw += w[i];
 
  
          backtrack(i+ 1);
 
  
          cw -= w[i];     }
 
  
       if (cw + r > bestw) {
 
  
          x[i] = 0; // 搜索右子树
 
  
          backtrack(i+ 1);      }
 
  
       r += w[i];
 
  
    }
 
  
 
  
 
 

源代码：

# include
# include
# include
#define M 1000

int w[M+100];
int n,bestw,curw,r;
int c1,c2;
char plag[M+100],bag[M+100];	//位置标记， 

int fun(int k)
{
	int i;
	if(k>=n)
	{
		if(curw>bestw)
		{
			for(i=0;ibestw)	//上界函数（剪枝函数）  
		{
			plag[k]=0;
			fun(k+1);
		}
		r+=w[k];	//状态恢复 
	}
	return 0;
}

int main(){
	
	int i;
	while(~scanf("%d%d",&c1,&c2))
	{
		memset(plag,0,sizeof(plag));				
		scanf("%d",&n);
		for(i=0;i 
  
 
  
 
   编辑于2015/2/13- 01：38