?

算法提高 01背包 ?

時間限制：1.0s ? 內(nèi)存限制：256.0MB

????

問題描述

　　給定N個物品,每個物品有一個重量W和一個價值V.你有一個能裝M重量的背包.問怎么裝使得所裝價值最大.每個物品只有一個.

輸入格式

　　輸入的第一行包含兩個整數(shù)n, m，分別表示物品的個數(shù)和背包能裝重量。
　　以后N行每行兩個數(shù)Wi和Vi,表示物品的重量和價值

輸出格式

　　輸出1行，包含一個整數(shù)，表示最大價值。

樣例輸入

3 5
2 3
3 5
4 7

樣例輸出

8

數(shù)據(jù)規(guī)模和約定

　　1<=N<=200,M<=5000.

?

#include<iostream> #include<algorithm> using namespace std; int w[210],v[210]; int dp[210][5010]; int ans=0; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i]>>v[i];for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);else dp[i][j]=dp[i-1][j];}cout<<dp[n][m]<<endl; }

空間復雜度還可以進一步優(yōu)化

#include<iostream> #include<algorithm> using namespace std; int w[210],v[210]; int dp[5010]; int ans=0; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i]>>v[i];for(int i=1;i<=n;i++)for(int j=m;j>=w[i];j--){dp[j]=max(dp[j-w[i]]+v[i],dp[j]);}cout<<dp[m]<<endl; }

優(yōu)化01背包的空間復雜度，對解決完全背包問題有一定的意義.

?

?

?

?

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的算法提高 01背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。