2020.12.30開(kāi)始學(xué)習(xí)AcWing算法《算法競(jìng)賽進(jìn)階指南》；
上傳博客方便復(fù)習(xí)。

多重背包問(wèn)題（N<= 100):

//Wecccccccc //2020.12.31 #include <iostream> using namespace std; int n,m,dp[110]; int main() {cin>>n>>m;for(int i=0;i<n;i++){int v,w,s;cin>>v>>w>>s;for (int j = m;j>=0;j--){for (int k = 1;k<=s && k * v <= j;k++){dp[j] = max(dp[j],dp[j-k*v]+k*w);}}}cout<<dp[m]<<endl;return 0; }

二進(jìn)制優(yōu)化(N<=1000)：

//Wecccccccc //2020.12.31 #include <iostream> using namespace std; #include <vector> struct GOOD {int v,w; };vector<GOOD> goods; int n,m,dp[2020]; int main() {cin>>n>>m;for(int i=0;i<n;i++){int v,w,s;cin>>v>>w>>s;for (int k = 1;k<=s;k*=2){s -=k;goods.push_back({v*k,w*k});}if (s > 0){goods.push_back({v*s,w*s});}}for (auto x : goods){for (int j = m;j>=x.v;j--){dp[j] = max(dp[j],dp[j-x.v]+x.w);}}cout<<dp[m]<<endl;return 0; }

多重背包問(wèn)題還有一種單調(diào)隊(duì)列優(yōu)化的方法，目前還沒(méi)學(xué)會(huì)（我是菜雞）。

總結(jié)

以上是生活随笔為你收集整理的多重背包问题以及二进制优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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