問題 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;}

?

總結

以上是生活随笔為你收集整理的【动态规划】0/1背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。