XDOJ（智慧平臺）--分配寶藏（用動態規劃dp演算法解決）(C語言)

------------------------------------------------------------
作為西電渣渣，這是我第一次接觸需要一些很明確的演算法的題目，

_{第一次博客寫廢話較多hhh，可以直接到下面看分析}

我在昨天晚上和舍友一起肝這道題，肝了一個晚上都沒有解決，甚至沒有一個很明確的思路，以至于躺在床上都想著怎么寫這道題 （畢竟智慧平臺上都會出現的題目，難道期末考試不會考嗎） 于是來社區看看有沒有西電學長 （其實更希望是學姐） 這里推一推學長的博客 XDU-分配寶藏，

但是本人看著稍微有點復雜的代碼就頭疼，于是去b站找了dp演算法的視頻動態規劃DP0-1背包，看了一半恍然大悟（假的）寫出來一個遞回函式交上去，發現一半的例子都超時了（淚目），看完視頻才知道dp演算法是怎么樣寫的，

然后就這樣心血來潮，寫下這篇博客，
本文章（大概、或許、可能）算是視頻和學長博客的結合吧，
------------------------------------------------------------

內容

一. Dynamic Programming (DP演算法)
二. 舉例（斐波那契數列，0-1背包）
三. 分配寶藏
------------------------------------------------------------

一、Dynamic Programming (DP演算法)

_{DP，聽起來挺高級的一個東西，我第一次接觸是在洛谷上，但是當時感覺學這玩意還早，就忽視了它，直到我在XDOJ上遇到了它，就有了這篇博客…}
DP，中文名譯為動態規劃，是求解決策程序最優化的程序，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態，又隨即引起狀態的轉移，一個決策序列就是在 變化的狀態中 產生出來的，故有“動態”的含義，（參考 百度百科—動態規劃）
下面將直接用例子來說明dp演算法，

二、舉例（斐波那契數列，0-1背包）

例1. 斐波那契數列

眾所周知，斐波那契數列是這樣的：
F(0)=1
F(1)=1
F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
實際上，這個公式就是一個遞回的思路，從我們需要求的那個值逐個歸回到F(0)和F(1)
由這個公式我們可以寫出一個遞回函式，其中遞回結束的標志是n=0或n=1.

int F(int n){
	int res;
	if(n<2) res=1;
	else res=F(n-1)+F(n-2);
	return res;
}
//再簡化一下可以寫成這樣
int F(int n){
	return n<2?1:F(n-1)+F(n-2);
}

又眾所周知,函式呼叫需要額外的空間（堆疊）來完成，在呼叫次數很多的情況下會降低程式效率，并且遞回呼叫可能會導致大量的重復計算，所以我們需要把這個遞回函式改造成一個效率更高的形式，
可以看到，遞回是從我們要的F(n)一直計算到F(0)和F(1)，然后再回傳到F(n)，在這個程序中，程式在不斷地分配空間，降低效率，那我們該怎么改才能提高效率呢？

舉個栗子，在Minecraft中，有一處懸崖，附近有一扇門，而門的鑰匙落在了懸崖底部，Steve需要取鑰匙開門，他有兩種方法，一個是遞回，一個是dp，

遞回意味著他從懸崖下去，但他不知道懸崖的高度，因此需要不斷地造梯子，爬下來，再回傳，來完成這個任務，

而dp，真是個好東西，它將Steve傳送到了懸崖的底部，并且告訴他懸崖的高度，這個時候，Steve只需要造一定數量的梯子直接搭上去完成任務，（咳咳，這個例子可能有點離譜，但是無傷大雅，dddd）

按照這個想法，遞回就相當于從高層走向底層，再回傳高層；dp就是從底層打基礎到高層，效率更高，
那如何打基礎呢？（再回到斐波那契數列）
我們知道當n>2的時候，F(n)=F(n-1)+F(n-2)，一直到F(0)和F(1)，而F(0)和F(1)就是最基礎的基礎，（這個時候有小伙伴就要說了，遞回函式不也有這個基礎嗎？答：不要在意這些細節~）dp就是要從基礎入手，又又眾所周知，要求F(n)，就要把F(n-1)到F(0)全部求一遍，那就求呀，由此我們可以寫出這么一段代碼：

int F[10000];					//陣列多大無所謂，只要夠用就行
F[0]=F[1]=1;					//初始化F[0]和F[1]
for(int i=2;i<=n;i++)        	//從F[2]開始到F[n]
	F[i]=F[i-1]+F[i-2];			//套公式

//改寫成函式
int Fib(int n){
	int F[10000]={1,1};
	for(int i=2;i<=n;i++)
		F[i]=F[i-1]+F[i-2];
	return F[n];
}

然后，dp這個方法就寫完了，然后可能有的小伙伴就懵了，直呼就這？
沒錯，就這，我們要的F[n]就出來了，
_{（這時候我突然想起，在剛學遞回的時候，其實就接觸到了這樣簡單的dp）}
實際上dp演算法就像學長@西電蔡徐坤所說的記憶化搜索一樣，取之前已經計算過的值，效率更高，
_{這時候就有小伙伴說了，那遞回豈不是一無是處，當然不是了，在很多演算法中，有遞回做得到而dp做不到的地方，以后或許能夠接觸到}

例2. 0-1背包問題

做完一維的，這個時候再來個二維豈不妙哉~

如圖所示，這就是一個經典的0-1背包問題，
我們設V為背包價值，k為能偷的物品數量，w為背包容量，w_i 為第 i 件物品的重量，v_i 為第i件物品的價值，則有V=V( k , w )，
在這題中，我們要求的就是V( 4 , 8 )，我們選擇從第k件（也就是第四件）開始偷，然后是k-1，k-2 … 2，1件，

從第4件物品開始，我們可以選擇偷和不偷，
①.如果選擇偷，那么V( 4 , 8 )=V( 4 - 1 , 8 - w₄ ) + v₄=V( 3 , 3 ) + 8
②.如果選擇不偷，則V( 4 , 8 )=V( 4 - 1 , 8 )=V( 3 , 8 )
取①的結果V( 3 , 3 ) + 8
③.發現這個時候的 w（背包容量）< w₃，因此只能選擇不偷，所以V( 3 , 3 ) + 8=V( 2 , 3 ) + 8
取②的結果V( 3 , 8 )
④.選擇偷，那么V( 3 , 8 )=V( 3 - 1 , 8 - w₃ ) + v₃=V( 2 , 4 ) + 5
⑤.選擇不偷，則V( 3 , 8 )=V( 3 - 1 , 8 )=V( 2 , 8 )
??????
這樣推下去，我們可以得到這樣的一個簡單公式

而我們要求的應該是最大值，再加上背包容量不夠的情況，得到狀態轉移方程

看到這里各位小伙伴是不是就可以寫一個遞回函式出來了，這里我就不再寫了（懶），
那這個遞回結束的標志應該是什么呢？
不難想到，當能偷的物品數量為0或者背包剩余容量為0時，遞回就該結束了，
因此V( k , 0 )=V( 0 , w )≡0
可以得到這么一個表格

由此按照例1的思想，是不是就直接能寫出代碼呢？
這里給出代碼片段，剩下的交給小伙伴們自己寫出來，

int v[5][9]={0};					
int w[]={0,2,3,4,5};
int v[]={0,3,4,5,8};
for(int k = 1; k <= 4; k++)						//k表示第k件物品
	for(int W = 1;W <= 8; W++){					//W表示背包剩余容量為W
		if(w[i]>W)								//物品重量大于背包剩余容量，不偷
			v[k][W]=v[k-1][W];
		else									//否則,從偷和不偷中選出最大值
			v[k][W]=max( v[k-1][W] ,v[k-1][W-w[k]]+v[k] );//max函式自己寫,或者用a?b:c運算式
	}											//v[4][8]就是要的答案

三、分配寶藏

事件的導火索可不能忘了

標題
分配寶藏
類別
綜合
時間限制
2s
記憶體限制
256Kb
問題描述
兩個尋寶者找到一個寶藏，里面包含n件物品，每件物品的價值分別是W[0]，W[1]，…W[n-1]，
SumA代表尋寶者A所獲物品價值總和，SumB代表尋寶者B所獲物品價值總和，請問怎么分配才能使得兩人所獲物品價值總和差距最小，即兩人所獲物品價值總和之差的絕對值|SumA - SumB|最小，
輸入說明
輸入資料由兩行構成：
第一行為一個正整數n，表示物品個數，其中0<n<=200，
第二行有n個正整數，分別代表每件物品的價值W[i]，其中0<W[i]<=200，

輸出說明
對于每組資料，輸出一個整數|SumA-SumB|，表示兩人所獲物品價值總和之差的最小值，

輸入樣例
4
1 2 3 4

輸出樣例
0

題目分析
這道題和例題2很像，但唯一不同的就是，物品的重量相當于價值，
題目要求A與B之差的絕對值最小，而物品總價值時固定的，因此將背包容量設為sum/2，

下面直接給出我的代碼（盡量用代碼里的注釋解釋代碼）

#include<stdio.h>
int W[201], sum, dp[201][20001];	//[201]是便于將物品從1開始編號
									//[20001]同理
int max(int a,int b);
int main(void)
{
	int n, i, j, sumA;				//假設A得到的永遠是較少的那個
	scanf( "%d", &n);
	for(i = 1; i <= n; i++){	i代指第i個物品
		scanf( "%d", &W[i] );
		sum += W[i];
	}
	for(i = 1; i <= n; i++){
		if (W[i] > sum/2){			//如果物品某個價值大于總價值的一半,其余物品將給A，不需要再計算
			dp[n][sum/2] =sum-W[i];
			break;
		}
		for(j = 1; j <= sum/2; j++){//j分別代指第i個物品和背包剩余容量
			if(W[i] > j) 			//同樣的，物品重量大于背包剩余容量，不偷
				dp[i][j] = dp[i-1][j];
			else 
				dp[i][j] = max( dp[i-1][j] , dp[i-1][j-W[i]] + W[i]);
		}
	}
	sumA = dp[n][sum/2];//個人比較喜歡單一出口
	printf("%d\n", sum - 2 * sumA);//因為A總是得到較少的那個，不需要再加上絕對值
	return 0;
}
int max(int a,int b){
	int m = a;
	if( a < b) m = b;
	return m;
}

這樣，這篇博客就到此結束了，希望對小伙伴們有一定幫助，同時也歡迎小伙伴們提出自己的想法和建議，