算法实验5《算法综合实验》

使用回溯法解决0-1背包问题

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int n, c, bestp;		//物品的个数，背包的容量，最大价值
     
    
   

    

     

    
    

     

      int p[80], w[80], x[80], bestx[80];		//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Backtrack(int i, int cp, int cw)
     
    
   

    

     

    
    

     

      { //cw当前包内物品重量，cp当前包内物品价值
     
    
   

    

     

    
    

     
	int j;
     
    
   

    

     

    
    

     
	if (i>n)//回溯结束
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (cp>bestp)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			bestp = cp;
     
    
   

    

     

    
    

     
			for (i = 0; i <= n; i++) bestx[i] = x[i];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     
	for (j = 0; j <= 1; j++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		x[i] = j;
     
    
   

    

     

    
    

     
		if (cw + x[i] * w[i] <= c)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cw += w[i] * x[i];
     
    
   

    

     

    
    

     

      			cp += p[i] * x[i];
     
    
   

    

     

    
    

     
			Backtrack(i + 1, cp, cw);
     
    
   

    

     

    
    

     

      			cw -= w[i] * x[i];
     
    
   

    

     

    
    

     

      			cp -= p[i] * x[i];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int _tmain(int argc, _TCHAR* argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	bestp = 0;
     
    
   

    

     

    
    

     

      	cout << "输入背包最大容量,物品个数,物品的重量,物品的价值\n";
     
    
   

    

     

    
    

     

      	cin >> c;
     
    
   

    

     

    
    

     

      	cin >> n;
     
    
   

    

     

    
    

     
	for (int i = 1; i <= n; i++)cin >> w[i];
     
    
   

    

     

    
    

     
	for (int i = 1; i <= n; i++)cin >> p[i];
     
    
   

    

     

    
    

     
	Backtrack(1, 0, 0);
     
    
   

    

     

    
    

     

      	cout << "最大价值为:" << bestp;
     
    
   

    

     

    
    

     
	printf("\n被选中的物品依次是\n");
     
    
   

    

     

    
    

     
	for (int i = 1; i <= n; i++)if (bestx[i])cout << "第" << i << "个物品" << endl;
     
    
   

    

     

    
    

     
	system("pause>nul");
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/78871857