背包問題---遞歸及動态規劃

一、原題

如果有一組物品，各個物品的品質已知，現有一個背包，背包可以容納的品質總和S已知，問是否能從這N個物品中取出若幹個恰好裝入這個背包中。

二、遞歸算法

本質思想：設法嘗試全部組合，當部分組合已經無法滿足條件時，馬上停止目前組合的嘗試；若出現第一個滿足條件的組合，馬上停止嘗試。使用遞歸回溯法實作。（感覺這東西不是我這樣的菜鳥可以說明确的，還得自己慢慢體會，最好的方法就是耐住性子跟蹤調試）。

上“酸菜”

#include <stdio.h>
#include <stdlib.h>

#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 <stdio.h>
#include <stdlib.h>

#define N 7
#define S 15
int 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<N+1;m++)
		{
			save[m]=0;
		}


		if(knap(S,i))
		{
			showSet();
			printf("\nOK!\n");
			//
			flag=true;								//當物品種類為i時，存在有效組合
		}
		else
		{
			//printf("\nNO!\n");
			flag=false;
		}
		
		//
		while(flag)
		{
			int j=N;
			int cnt=0;
			int s_index=0;
			while(j!=0 && cnt!=2)
			{
				if(save[j]==1)
				{
					cnt++;
				}
				if(cnt==1)
				{
					s_index=j;
				}
				j--;
			}
			if(cnt==2)
			{
				for(int k=0;k<s_index;k++)
				{
					save[k]=0;
				}

				if(knap(S-w[s_index],j))				//從有效組合第二個物品的下一個物品開始尋找
				{
					showSet();
					printf("\nOK!\n");
				}
				else
				{
					flag=false;
				}
				
			}
			else
			{
				flag=false;
			}
		}

	}

	system("pause");
	return 0;
}      

舉例來講，因為第一個有效的組合是7，2，5，1，所下面一次從2的下一個數開始搜尋，背包的容量變成8=15-7.

三、動态規劃方法

詳見參考1，這裡可以将物品的品質作為它的價值，那麼假設最大價值dp[N][S]等于S，則說明背包可以恰好裝滿。

#include <iostream>
using namespace std;
#define N 7
#define S 15
#define max(a,b) a>b?a:b

int 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<S+1;j++)
		{
			if(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;
}      

四、其他背包相關問題