用C语言回溯法解决01背包问题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 5


//0-1背包，用三种算法实现
//动态规划，贪心，回溯，分支限界

void Output(int bestx[]);
int Constraint(int t);
float Bound(int i);
void BackTrack(int i);


int cp = 0, cw = 0;
int bestp = 0;//最好重量
int c = 17;
int x[N] = { 0 };//解向量
int w[N] = { 3,4,5,10,8 };//物品重量
int p[N] = { 5,6,10,30,17 };//物品价值
int bestx[N] = { 0 };


int main()
{
	//int bestx[N] = { 0 };
	BackTrack(0);
	for (int i = 0; i < N; i++)
	{
		printf("%d ", bestx[i]);
	}
	printf("%d", bestp);
	return 0;
}

void Output()
{
	int price = 0;
	for (int i = 0; i < N; i++)//一个一个尝试
	{
		if (x[i])
		{
			price = price + p[i];
		}
		if (price > bestp)
		{
			bestp = price;
			for (int j = 0; j < N; j++)
			{
				bestx[j] = x[j];
			}
		}
	}
}

int Constraint(int t)
{
	int contain = 0;
	for (int i = 0; i <= t; i++)
	{
		if (x[i])
		{
			contain = contain + w[i];
		}
		if (contain <= c)
		{
			return 1;
		}
		else
			return 0;
	}
}

void BackTrack(int i)
{
	if (i == N)//到达叶子结点
	{
		if (cp >= bestp)
		{
			bestp = cp;
			for (i = 0; i < N; i++)
			{
				bestx[i] = x[i];
			}
		}
		return;
	}
	if (cw + w[i] <= c)//左子树
	{
		x[i] = 1;
		cw += w[i];
		cp += p[i];
		BackTrack(i + 1);
		cw -= w[i];
		cp -= p[i];
	}
	if (Bound(i+1) > bestp)//右子树
	{
		x[i] = 0;
		BackTrack(i + 1);
	}
}



//最大重量
float Bound(int i)
{
	float cleft = c - cw;
	float b = cp;
	while (i < N && w[i] <= cleft)
	{
		cleft -= w[i];
		b += p[i];
		i++;
	}
	if (i < N)
	{
		b += p[i] / w[i] * cleft;
	}
	return b;
}