題目來自JZYZOJ。找了很多地方都沒有找到題，還是一道非常優秀的二進制優化多重背包的問題

---

描述 Description

在《Harry Potter and the Deathly Hallows》中，Harry Potter他們一起逃亡，現在有許多的東西要放到赫敏的包里面，但是包的大小有限，所以我們只能夠在里面放入非常重要的物品，現在給出該種物品的數量、體積、價值的數值，希望你能夠算出怎樣能使背包的價值最大的組合方式，并且輸出這個數值，赫敏會非常地感謝你。

---

輸入格式 Input Format

第\(1\)行有\(2\)個整數，物品種數\(n\)和背包裝載體積\(v\)。

第\(2\)行到\(n+1\)行每行\(3\)個整數，為第\(i\)種物品的數量\(m\)、體積\(w\)、價值\(s\)。

---

輸出格式 Output Format

僅包含一個整數，即為能拿到的最大的物品價值總和。

---

樣例輸入 Sample Input

2 10 3 4 3 2 2 5

---

樣例輸出 Sample Output

13

注釋 Hint

對于$ 100% $的數據

$1 \le v \le 5000 $

$1 \le n \le 5000 $

$1 \le m \le 5000 $

$1 \le w \le 5000 $

$1 \le s \le 5000 $

---

如果數據范圍比較小的話可以直接多重背包但這道題數據很大自然要用到二進制優化

對于多重背包，枚舉每一種物品的每一種數量自然是多次重復的運算

我們已知\(1\) , \(2\) , \(4\) , \(8\) , \(16\) , \(32……\),\(2^n\)可以組成\(1\)到\(2^{n+1}-1\)之內的任意一個數字

所以我們對于給定\(n\),把他分解成\(2^x\)的數，剩下的數進行補齊，即可轉換成01背包做

轉換代碼

for(register int i = 1;i <= n;i++) {for(register int j = 1;j <= m[i];j <<= 1){tw[++tot] = j*w[i];tv[tot] = j*v[i];m[i] -= j;}if(m[i])//補齊剩下的數{tw[++tot] = m[i]*w[i];tv[tot] = m[i]*v[i];} }

另外新的數組\(tw,tv\)要開成原數組的\(max(x)\)倍

---

coding

#include <bits/stdc++.h> using namespace std;const int N = 5005; int n,V,tot = 0,v[N] = {},m[N] = {},w[N] = {}, tw[N*20] = {},tv[N*20] = {},f[N] = {};inline int read() {register int x = 0;register char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9'){x = (x<<3) + (x<<1) + ch-'0';ch = getchar();}return x; }inline void optimize() {for(register int i = 1;i <= n;i++){for(register int j = 1;j <= m[i];j <<= 1){tw[++tot] = j*w[i];tv[tot] = j*v[i];m[i] -= j;}if(m[i]){tw[++tot] = m[i]*w[i];tv[tot] = m[i]*v[i];}} }int main() {n = read(); V = read();for(register int i = 1;i <= n;i++) m[i] = read(), w[i] = read(), v[i] = read();optimize();for(register int i = 1;i <= tot;i++){for(register int j = V;j >= tw[i];j--) f[j] = max(f[j],f[j-tw[i]]+tv[i]);}printf("%d\n",f[V]);return 0; }

轉載于:https://www.cnblogs.com/Mark-X/p/11404648.html

總結

以上是生活随笔為你收集整理的逃亡的准备（大数据版）的全部內容，希望文章能夠幫你解決所遇到的問題。

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