回溯法解决01背包问题

输入（共n+1行）:物品数量、背包体积

下面n行依次输入物品价值和体积

需要注意的点:

①输入的顺序

②存储价值和体积的数组下标从1开始

③每一轮符合条件时，及时更新VALUE（价值总和）

从前面做的回溯法可以总结出一些回溯法做题的思路，虽然回溯法在实际运用中很少运用，但是它可以帮我们理解递归的执行过程。

回溯法做题思路：

①确定问题：求最优解/求符合条件的所有解

②开辟数组：

如果问题是求最优解，那么一般需要有两个数组A和B，一个数组A供递归时暂时存放数据，另一个数组B用来存储答案，在满足条件时更新B

如果问题时求符合条件的所有解，那么回溯的过程只需要一个暂时存放数据的数组就可以了，当满足条件时输出数组里面的数据（因为问题的解可能有多个，我们只需要输出不需要保存）

③在执行完递归之后，要及时“恢复现场”，保证下一轮递归不受影响

#include<iostream>
using namespace std;
const int N=100;
int v[N],s[N];
int t[N],ans[N];
int VALUE=-INT_MAX,SIZE=0,MAXSIZE=0;
int n;
/*
5 12
1 1
2 3
3 2
4 5
6 5
*/
/*
4 5
2 1
4 2
4 3
5 4
*/
void solve(int k)//k表示物品 
{
	for(int i=0;i<=1;i++)//i表示选或者不选,1选0不选
	{
		t[k]=i;
		
		int tvalue=0,tsize=0;
		for(int j=1;j<=n;j++)
		{
			tvalue+=t[j]*v[j];
			tsize+=t[j]*s[j];
		}
			
		if(k!=n)
		{
			solve(k+1);
			t[k]=0;
		}	
		else if(k==n&&tvalue>VALUE&&tsize<=MAXSIZE)
		{	
		
				VALUE=tvalue;//至关重要,更新最大价值总和 
				
				for(int j=1;j<=n;j++)
					ans[j]=t[j];
					
//				printf("价值总和tvalue=%d,体积总和tsize=%d\n",tvalue,tsize);
//				for(int j=1;j<=n;j++)
//				{
//					if(t[j]==0)
//						printf("物品%d不选\n",j);
//					else if(t[j])
//						printf("选择物品%d,该物品价值为:%d,体积为:%d\n",j,v[j],s[j]);
//				}
//			}
			//恢复现场 
			t[k]=0;
		}
	} 
}
int main()
{
	cin>>n>>MAXSIZE;
	
	for(int i=1;i<=n;i++)//下标从1开始 
		scanf("%d%d",&v[i],&s[i]);//注意,先输入价值再输入体积 
		
	solve(1);
	
	int tvalue=0,tsize=0;
	
	for(int j=1;j<=n;j++)
	{
		tvalue+=ans[j]*v[j];
		tsize+=ans[j]*s[j];
	}
	printf("--------最终选择策略--------\n");
	printf("价值总和tvalue=%d,体积总和tsize=%d\n",tvalue,tsize);
	for(int j=1;j<=n;j++)
	{
		if(ans[j]==0)
			printf("物品%d不选\n",j);
		else if(ans[j])
			printf("选择物品%d,该物品价值为:%d,体积为:%d\n",j,v[j],s[j]);
	}
	
	return 0;
} 

运行结果：