ACM競賽學習整理開篇之01背包問題。

最近，偶然的一次機會讓我關注信息奧賽的一些內容。發現其中的內容很有趣，是學習編程的一條很好的路徑，又能很好地將數學和編程聯系到一起。在csdn里看到了不少同好也在學習ACM競賽。于是，決定通過csdn這個平臺來記錄，我的ACM學習之路。

背包問題：

背包問題已經研究了一個多世紀，早期的作品可追溯到1897年 [1] 數學家托比亞斯·丹齊格（Tobias Dantzig，1884-1956）的早期作品 [2] ，并指的是包裝你最有價值或有用的物品而不會超載你的行李的常見問題。

背包問題的應用：

1998年的石溪布魯克大學算法庫的研究表明，在75個算法問題中，背包問題是第18個最受歡迎，第4個最需要解決的問題（前三為后kd樹，后綴樹和bin包裝問題）。
背包問題出現在各種領域的現實世界的決策過程中，例如尋找最少浪費的方式來削減原材料， [4] 選擇投資和投資組合， [5] 選擇資產支持資產證券化 [6] ，和生成密鑰為Merkle-Hellman [7] 和其他背包密碼系統。

在ACM競賽中設計的背包問題有：

先了解下3種簡單的背包概念:

0-1背包 (ZeroOnePack): 有N件物品和一個容量為V的背包。每種物品均只有一件 第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
多重背包 (MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用， 每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。*

比較三個題概念，會發現不同點在于每種背包的數量，01背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。

**

01 背包

1、OJ 例題
【例題】
有n個物品，編號為i的物品的重量為w[i]，價值為c[i]，現在要從這些物品中選一些物品裝到一個容量為m的背包中，使得背包內物體在總重量不超過m的前提下價值盡量大。
【輸入】
第1行:兩個整數，n(物品數量，n≤3500)和m(背包容量,m≤12880)。
第2…n+1行：：每行二個整數w[i]，c[i]，表示每個物品的重量和價值。
【輸出】
僅一行，一個數，表示最大總價值。
【輸入樣例】
4 6
1 4
2 6
3 12
2 7
【輸出樣例】
23

2、 解題思路：

用動態規劃的思路，階段就是“物品的件數”，狀態就是“背包剩下的容量”，那么很顯然f [ i , v ] 就設為從前 i 件物品中選擇放入容量為 v 的背包最大的價值。那么狀態轉移方程為：

f[i][v]=max{ f[i-1][v],f[i-1][v-w[i]]+val[i] }。

把這個過程理解下：在前i件物品放進容量v的背包時，

它有兩種情況：

第一種是第i件不放進去，這時所得價值為:f[i-1][v]

第二種是第i件放進去，這時所得價值為：f[i-1][v-w[i]]+val[i]

（第二種是什么意思？就是如果第i件放進去，那么在容量v-w[i]里就要放進前i-1件物品）

最后比較第一種與第二種所得價值的大小，哪種相對大，f[i][v]的值就是哪種。

（這是基礎，要理解！）

3、 代碼求解：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int m,n; int w[N],c[N],f[N];void ZeroOnePack(int cost,int weight) {for(int v=m;v>=weight;v--){f[v]=max(f[v],f[v-weight]+cost);cout<<"f["<<v<<"]"<<"="<<f[v]<<" ";}cout<<endl; }int main() {cin>>m>>n;for(int i=1;i<=n;i++)cin>>w[i]>>c[i];cout<<endl;for(int i=1;i<=n;i++)ZeroOnePack(c[i],w[i]);cout<<"max="<<f[m]<<endl;return 0; }

4、結果輸出

5、反思總結

背包問題是貪心算法的實例，可以根據動態規劃解題步驟來實現

（問題抽象化、建立模型、尋找約束條件、判斷是否滿足最優性原理、找大問題與小問題的遞推關系式、填表、尋找解組成）找出01背包問題的最優解以及解組成，然后編寫代碼實現。

回顧01背包的定義：

PS：學習的心得比較難寫，我將代碼放到了C-free開發環境中試驗了下，然后把計算的結果打印在了屏幕上，然后草稿紙上將其步驟再簡單畫了畫，最后在網上查找了相關的內容來幫助理解，以上內容，基本上還是復制粘貼，等后續實際問題再操練吧。
這里有杭電OJ上的一道例題供大家參考：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代碼：http://www.wutianqi.com/?p=533

參考文檔：

1、https://blog.csdn.net/weixin_41162823/article/details/87878853背包問題-筆記整理

2、https://blog.csdn.net/qq_37767455/article/details/9908667801背包問題 圖解+詳細解析

3、http://www.wutianqi.com/blog/539.html背包之01背包、完全背包、多重背包詳解

4、https://blog.csdn.net/chanmufeng/article/details/82955730徹底理解0-1背包問題

總結

以上是生活随笔為你收集整理的ACM竞赛学习整理开篇之01背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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