アルゴリズム実験5『アルゴリズム総合実験』

#include
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;
}