資訊學奧賽一本通 1267：01背包問題（evd）

【題目描述】

一個旅行者有一個最多能裝 M 公斤的背包，現在有 n 件物品，它們的重量分别是W1，W2，…,Wn,它們的價值分别為C1,C2,…,Cn，求旅行者能獲得最大總價值。

【輸入】

第一行：兩個整數，M(背包容量，M≤200)和N(物品數量，N≤30)；

第2…N+1行：每行二個整數Wi，Ci，表示每個物品的重量和價值。

【輸出】

僅一行，一個數，表示最大總價值。

【輸入樣例】

10 4

2 1

3 3

4 5

7 9

【輸出樣例】

12

【心得】背包的鼻祖！跟包的順序無關，隻要能裝下，就一直更新最優值！

【AC代碼】

#include<iostream>
using namespace std;
int c[35],f[205],w[35];
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
	for(int i=1;i<=n;i++)
		for(int j=m;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+c[i]);
	cout<<f[m];
	return 0;
}