可以刷armbian的盒子，hihoCoder-1038- 01背包（dp）

???????????????????????????????????????????????????????????? 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

題意描述：

給你n種物品每種物品有一件和一個容量為m的背包然后給你每種物品的體積和價值求背包所能容下的最大價值

程序代碼：

#include<stdio.h>
#include<algorithm>
using namespace std;
#include<string.h>
int v[520],w[520],dp[100010];
int main()
{int n,m,i,j,count;while(scanf("%d%d",&n,&m)!=EOF){memset(dp,0,sizeof(dp));for(i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);for(i=1;i<=n;i++)for(j=m;j>=v[i];j--)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);printf("%d\n",dp[m]);		}return 0;
}

?