一、原题

如果有一组物品，各个物品的质量已知，现有一个背包，背包可以容纳的质量总和S已知，问是否能从这N个物品中取出若干个恰好装入这个背包中。

二、递归算法

本质思想：设法尝试全部组合，当部分组合已经无法满足条件时，马上停止当前组合的尝试；若出现第一个满足条件的组合，马上停止尝试。使用递归回溯法实现。（感觉这东西不是我这样的菜鸟可以说明确的，还得自己慢慢体会，最好的方法就是耐住性子跟踪调试）。

上“酸菜”

#include 
     
      #include 
      
       #define N 7						//物品种类#define S 15					//背包容量int w[N+1]={0,1,4,3,4,5,2,7};	//各种物品的质量bool knap(int s,int n)			//s代表背包剩余容量，n代表还未尝试装载的物品种类{	if(s==0)					//恰好装完	{		return true;	}	if(s<0 || (s>0 && n<1))		//不能完毕装载	{		return false;	}		if(knap(s-w[n],n-1))		//当前物品可以装载，则递归	{		printf("%d	",w[n]);		return true;	}	else	{		return knap(s,n-1);		//当前物品不能装载，取下一物品进行递归	}}int main(void){	if(knap(S,N))	{		printf("OK!!!\n");	}	else	{		printf("NO!!!\n");	}		system("pause");	return 0;}
      
     

上面的代码只输出了第一个满足条件的组合，那么如何输出所有的有效组合呢？

#include 
     
      #include 
      
       #define N 7#define S 15int w[N+1]={0,1,4,3,4,5,2,7};//int save[N+1]={0};			//标记数组int knap(int s,int n){	if(s==0)	{		return 1;	}	if(s<0 || (s>0 && n<1))	{		return 0;	}	if(knap(s-w[n],n-1))	{		//printf("%4d",w[n]);		//		save[n]=1;		return 1;	}	return knap(s,n-1);}void showSet(void){	for(int i=N;i>0;i--)	{		if(save[i]==1)		{			printf("%4d",w[i]);		}	}}int main(void){	bool flag;	for(int i=N;i>0;i--)					//不断降低物品的种类，以便遍历全部组合	{		//		for(int m=0;m
      
     

举例来讲，因为第一个有效的组合是7，2，5，1，所下面一次从2的下一个数開始搜索，背包的容量变成8=15-7.

三、动态规划方法

详见，这里可以将物品的质量作为它的价值，那么假设最大价值dp[N][S]等于S，则说明背包可以恰好装满。

#include 
     
      using namespace std;#define N 7#define S 15#define max(a,b) a>b?a:bint w[N+1]={0,1,4,3,4,5,2,7};	//各种物品的质量int main(void){	int i,j;	int dp[N+1][S+1];	memset(dp,0,sizeof(dp));	for(i=1;i<=N;i++)	{		for(j=0;j
      
       =w[i])			{				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);		//转移方程，当中w[i]能够看做各物品的价值			}			else			{				dp[i][j]=dp[i-1][j];			}		}	}	printf("%d\n",dp[N][S]);	if(dp[N][S]==S)	{		printf("OK!!!\n");	}	else	{		printf("NO!!!\n");	}	system("pause");	return 0;}
      
     

四、其他背包相关问题

依据以上分析，加以变通就可以。