問題 H: 【動態規劃】0/1背包問題
時間限制: 1 Sec??內存限制: 64 MB
提交: 152??解決: 95
[提交] [狀態] [討論版] [命題人:admin]
?
題目描述
張琪曼和李旭琳有一個最多能用m公斤的背包，有n塊魔法石，它們的重量分別是W1，W2，…，Wn，它們的價值分別為C1，C2，…，Cn。若每種魔法石只有一件，問能裝入的最大總價值。
?
輸入
第一行為兩整數m和n，以下n行中，每行兩個整數Wi，Ci，分別代表第i件物品的重量和價值。
?
輸出
輸出一整數，即最大價值。
?
樣例輸入
8 3
2 3
5 4
5 5
?
樣例輸出
8
AC代碼
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n,v;int w[100100],c[100100];int f[100100];int zeroone(){for(int i=1;i<=n;i++)for(int j=v;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);return f[v];}int main(){cin>>v>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];cout<<zeroone()<<endl;return 0;}| ? |
)
