算法实验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 << "输入背包最大容量,物品个数,物品的重量,物品的价值
";
	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("
被选中的物品依次是
");
	for (int i = 1; i <= n; i++)if (bestx[i])cout << "第" << i << "个物品" << endl;
	system("pause>nul");
	return 0;
}