算法实验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