01背包的深度優先搜尋

1. 問題描述：

有n件物品，每件物品的重量是w[i]，價值為c[i]，現在有一個容量為V的背包，問如何選取物品放入到背包中使得背包内物品的總價值是最大的，其中每種物品都是隻有一件的 

2. 思路分析：

對于01背包問題，是條件比較簡單的背包問題，典型和高效的解法是使用使用動态規劃的思想，求出狀态方程來進行求解，但是對于這一類可以使用動态規劃的最優問題我們也可以使用深度優先搜尋來進行解決，可以鍛煉我們思考問題的方式，下面是具體的思路：

① 首先要确定多少個平行狀态，平行狀态可以表示可以遞歸調用的次數，比如對于這道題目來說，對于目前的物品我們可以選擇也可以不選，那麼就存在着兩種平行狀态，是以對應着兩次遞歸調用自己

② 确定方法中需要傳遞的參數，因為對于目前的物品我隻能夠選擇一次，是以需要記錄一下目前物品的編号，還需要記錄的是目前背包放的容量是多少了，目前背包容量的價值，這些變量都需要作為參數傳遞進遞歸的方法中

③ 接下來就是确定出口了，我們知道當我們對于最後一件物品來進行選擇的時候那麼就到了遞歸的出口，也就是當目前記錄的編号等于物品的件數的時候那麼就可以層層進行傳回了（return）

④ 剪枝的問題，我們之前的寫法可以是不使用if判斷來遞歸調用，也就是隻使用兩個方法進行遞歸調用知道到達遞歸的出口但是這會造成某些已經不滿足條件了但是還是往下進行遞歸調用是以造成了不必要的計算，是以我們在選擇了目前的物品之前需要判斷一下加上目前物品的重量之後那麼會不會超出背包的容量

3. 下面是具體的C++代碼，存在兩種風格的寫法，一種是在遞歸的出口來确定是否更新最大值，另外一種是在判斷可以假如目前的物品之後來确定是否更新最大值，第一種寫法是當我到達遞歸出口的時候那麼之前的累加的物品的價值就知道了，是以可以決定是否更新目前背包容量的最大價值，而後一種方法我的了解是層層傳回的時候進行最大價值的更新，也是可以的，考慮問題的方式不一樣而已

測試資料如下：

5 8 
3 5 1 2 2
4 5 2 1 3
           

輸出10

#include<stdio.h>
using namespace std;
const int maxn = 30;
int n, V, ans = 0;//物品件數n, 背包容量V,最大價值maxvalue 
int w[maxn], c[maxn];  //w[i]為每件物品的重量,c[i]為每件物品的價值 
//sumW和sumC為目前總重量和總價值
void dfs(int index, int sumW, int sumC){
	if(index == n){
		return;
	}
	//通過下面的剪枝之後那麼就可以限制一些沒有必要的搜尋 
	dfs(index + 1, sumW, sumC);
	if(sumW + w[index] <= V){
		if(sumC + c[index] > ans){
			ans = sumC + c[index];
		}
		dfs(index + 1, sumW + w[index], sumC + c[index]);
	}	
}
 
int main(void){
	scanf("%d%d", &n, &V);
	for(int i = 0; i < n; i++){
		scanf("%d", &w[i]);
	}
	for(int i = 0; i < n; i++){
		scanf("%d", &c[i]);
	}
	dfs(0, 0, 0);
	printf("%d\n", ans); 
	return 0;
} 
           

#include<stdio.h>
using namespace std;
const int maxn = 30;
int n, V, ans = 0;//物品件數n, 背包容量V,最大價值maxvalue 
int w[maxn], c[maxn];  //w[i]為每件物品的重量,c[i]為每件物品的價值 
//sumW和sumC為目前總重量和總價值
void dfs(int index, int sumW, int sumC){
	if(index == n){
		if(sumC > ans){
			ans = sumC;
		}
		return;
	}
	dfs(index + 1, sumW, sumC);
	
	//使用if條件進行限制(剪枝) 
	if(sumW + w[index] <= V){
		dfs(index + 1, sumW + w[index], sumC + c[index]);
	}	
}
 
int main(void){
	scanf("%d%d", &n, &V);
	for(int i = 0; i < n; i++){
		scanf("%d", &w[i]);
	}
	for(int i = 0; i < n; i++){
		scanf("%d", &c[i]);
	}
	dfs(0, 0, 0);
	printf("%d\n", ans); 
	return 0;
}