問題 O: 【動態規劃】完全背包問題
時間限制: 1 Sec??內存限制: 64 MB
提交: 151??解決: 71
[提交] [狀態] [討論版] [命題人:admin]
?
題目描述
話說張琪曼和李旭琳又發現了一處魔法石礦（運氣怎么這么好？各種嫉妒羨慕恨啊），她們有一個最多能裝m公斤的背包，現在有n種魔法石，每種的重量分別是W1，W2，…，Wn，每種的價值分別為C1，C2，…，Cn。若每種魔法石的個數足夠多，求她們能獲得的最大總價值。
?
輸入
第一行為兩個整數，即m，n。
以后每行為兩個整數，表示每塊魔法石的重量和價值。
?
輸出
獲得的最大總價值。
?
樣例輸入
5 5
1 1
2 2
3 3
4 4
5 5
?
樣例輸出
5
AC代碼
#include <cstdio>#include <algorithm>#include <cstring>#include <iostream>using namespace std;int w[100100],c[100100];int f[100100];int n,v;int complete(){for(int i=1;i<=n;i++)for(int j=w[i];j<=v;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<<complete()<<endl;return 0;}| ? |
)
)
