hihoCoder - 1038 - 01背包 （經典動態規劃問題！！）

hihoCoder - 1038 - 01背包 （經典動態規劃問題！！）

#1038 : 01背包

描述

且說上一周的故事裡，小Hi和小Ho費勁心思終於拿到了茫茫多的獎券！而現在，終於到了小Ho領取獎勵的時刻了！

小Ho現在手上有M張獎券，而獎品區有N件獎品，分別標號為1到N，其中第i件獎品需要need(i)張獎券進行兌換，同時也只能兌換一次，為了使得辛苦得到的獎券不白白浪費，小Ho給每件獎品都評了分，其中第i件獎品的評分值為value(i),表示他對這件獎品的喜好值。現在他想知道，憑借他手上的這些獎券，可以換到哪些獎品，使得這些獎品的喜好值之和能夠最大。

提示一：合理抽象問題、定義狀態是動態規劃最關鍵的一步

提示二：說過了減少時間消耗，我們再來看看如何減少空間消耗

輸入

每個測試點（輸入文件）有且僅有一組測試數據。

每組測試數據的第一行為兩個正整數N和M,表示獎品的個數，以及小Ho手中的獎券數。

接下來的n行描述每一行描述一個獎品，其中第i行為兩個整數need(i)和value(i)，意義如前文所述。

測試數據保證

對於100%的數據，N的值不超過500，M的值不超過10^5

對於100%的數據，need(i)不超過2*10^5, value(i)不超過10^3

輸出

對於每組測試數據，輸出一個整數Ans，表示小Ho可以獲得的總喜好值。

樣例輸入

5 1000
144 990
487 436
210 673
567 58
1056 897

樣例輸出

2099

最初我最怕做的就是DP的題目了，，因為一直沒學太懂，，額，，現在也沒學太懂。。

 

DP：

什麼樣算是一個子問題？

首先，我們要想辦法把我們現在遇到的問題給抽象化！

以best(i, x)表示已經決定了前i件物品是否選取，當前已經選取的物品的所需獎券數總和不超過x時，能夠獲取的最高的喜好值的和。

所以有best(N, M) = max{best(N - 1, M - need(N)) + value(N), best(N - 1, M)}！

對於任意i>1, j，我們都可以知道best(i, j)=max{best(i-1, j-need(i)) + value(i), best(i - 1, j)}!

 

這個01背包問題可以分二維和一維來做，果然一維更巧妙

 

二維AC代碼（672ms，200MB）：

 

#include 
#include 
#include 
using namespace std;

int dp[502][100002];
int need[502], value[502];

int main()
{
	int n, m;
	while(scanf(%d %d, &n, &m) != EOF)
	{
		for(int i=1; i<=n; i++)
			scanf(%d %d, &need[i], &value[i]);
		for(int j=0; j<=m; j++)
			dp[0][j] = 0;
		for(int i=1; i<=n; i++)
			for(int j=0; j<=m; j++)
				if(j
 
一維AC代碼：
 
#include 
#include 
#include 
using namespace std;

int dp[100005];
int need[502], value[502];

int main()
{
	int n, m;
	while(scanf(%d %d, &n, &m) != EOF)
	{
		for(int i=1; i<=n; i++)
			scanf(%d %d, &need[i], &value[i]);
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++)
			for(int j=m; j>=need[i]; j--)
				dp[j] = max(dp[j], dp[j-need[i]] + value[i]);
		printf(%d
, dp[m]);
	}
	return 0;
}