01背包回溯+递归解法_利用回溯法的递归框架,实现 01 背包问题,(问题设定:背包的限定重 量为 6,物品数量

    学校的算法实验，用回溯和递归求解01背包问题。觉得回溯思路不适合解01背包问题，因为01背包问题中掺杂了两个变量：背包容量和携带的价值（价值比较出最大价值），但毕竟是学校实验，还是得做啊。

    我的思路是，设一个数组，长度为物品的数量。数组为赋值为0，则表示当前物品不取；赋值为1，则取。然后对每一位遍历，最后比较。用动态做最省事。

回溯代码：

#include <stdio.h>
#include <malloc.h>
#define M 5
int *choice,*saved;
int maxV = -1;
void KNAPSACK(int *v,int *s,int C,int n);
int main(void)
{
	int s[M] = {3,5,7,8,9},v[M] = {4,6,7,9,10},C = 11;
	int i=0,sum=0;
	KNAPSACK(v,s,C,M);
	printf("选择");
	for(i=0;i<M;i++)
	{
		if(saved[i])
		{
			printf("第%d项,",i+1);
			sum+=s[i];
		}
	} 
	printf("物品放入背包,");
	printf("物品总体积为:%d,总价值为%d.",sum,maxV);
	return 0;
}
//v数组价值，s数组体积，C背包容量，n数量 
void KNAPSACK(int *v,int *s,int C,int n)
{
	choice = (int*)malloc(sizeof(int)*(n+1));
	saved = (int*)malloc(sizeof(int)*(n+1));
	int flag = 0;
	int i=0,j=0,k=0;
	int value=0,bag=0;
	for(i=0;i<n;i++)
		choice[i]=-1,saved[i]=-1;
	while(k>=0)
	{
		while(choice[k]<1)   //筛选每一个物品，两种可能，取或者不取分别对应0/1 
		{
			choice[k]++;
			if(k==n)
			{
				value=0,bag=0;
				for(i=0;i<n;i++)
				{
					if(choice[i])
					{
						bag+=s[i];
						value+=v[i];
					}
				}
				if(maxV<value&&bag<=C)
				{
					maxV = value;
					for(i=0;i<n;i++) saved[i] = choice[i];
				}
				break;
			}
			else k++;
		}
		choice[k] = -1;
		k--;
	}
} 

递归代码：

#include <stdio.h>
#include <malloc.h>
#define M 5
int *choice,*saved;
int maxV = -1;
void KNAPSACK(int *v,int *s,int C,int cur);
int main(void)
{
	int s[M] = {3,5,7,8,9},v[M] = {4,6,7,9,10},C = 11;
	choice = (int*)malloc(sizeof(int)*M);
	saved = (int*)malloc(sizeof(int)*M);
	int i=0,sum=0;
	KNAPSACK(v,s,C,0);
	printf("选择");
	for(i=0;i<M;i++)
	{
		if(saved[i])
		{
			printf("第%d项,",i+1);
			sum+=s[i];
		}
	} 
	printf("物品放入背包,");
	printf("物品总体积为:%d,总价值为%d.",sum,maxV);
	return 0;
}
//v数组价值，s数组体积，C背包容量，cur当前位 
void KNAPSACK(int *v,int *s,int C,int cur)
{
	if(cur==M-1)
	{
		int value=0,bag=0,i=0;
		for(i=0;i<M;i++)
		{
			if(choice[i])
			{
				bag+=s[i];
				value+=v[i];
			}
		}
		if(maxV<value&&bag<=C)
		{
			maxV = value;
			for(i=0;i<M;i++) saved[i] = choice[i];
		}
		return;
	}
	else
	{
		choice[cur] = 0;
		KNAPSACK(v,s,C,cur+1);
		choice[cur] = 1;
		KNAPSACK(v,s,C,cur+1);
	}
}