编辑代码

#include <stdio.h>
 
#define N 4        //物品的数量
#define C  10       
 
int w[N] = { 2, 6, 5, 4};  //每个物品的重量
int v[N] = { 3, 5, 4, 6};   //每个物品的价值
int x[N] = { 0, 0, 0, 0};   
 
int cur_weight = 0;  
int cur_value = 0;   
int best_value = 0;  
int best_x[N];       
//t = 0 to N-1
void backtrack(int t)
{
	int i;

	//叶子节点，输出结果
	if(t > N - 1) 
	{
		//如果找到了一个更优的解
		if(cur_value > best_value)
		{
			//保存更优的值和解
			best_value = cur_value;
			for(i = 0; i < N; ++i) 
			{
				best_x[i] = x[i];
			}
		}
	}
	else
	{
		//遍历当前节点的子节点：0 不放入，1放入
		for(i = 0; i <= 1; ++i)
		{
			x[t] = i;
 
			if(i == 0)         
			{
				backtrack(t + 1);
			}
			else               
			{
 				//约束条件：放的下
				if((cur_weight + w[t]) <= C)
				{
					cur_weight += w[t];
					cur_value += v[t];
					backtrack(t + 1);
					cur_weight -= w[t];
					cur_value -= v[t];
				}
			}
		}
	}
}
 
 //回溯法解决问题
int main(int argc, char* argv[])
{
	int i; 
	
	backtrack(0);
 
	printf("最大值：%d\n",best_value);
 
	for(i = 0; i < N; i++)
	{
	   printf("%-3d", best_x[i]);
	}

	return 0;
}