01背包，01背包問題

01背包，01背包問題

以前在acm課上也講過一些關於背包的題，不過那些比較簡單，就是簡單的貪心問題，先排個序再處理就完了，而01背包，感覺就是比那個上了一個難度的問題，這個需要遍歷然後找其中合適的，簡單原理就是這樣。

例如：現在有容量為m的背包，還有重量為w，價值為v的k個不同的商品，問怎樣買才能使價值最大化？

  思路：如果是貪心問題就是直接將商品按價格從大到小排序，然後依次買，顯然這樣是錯的，我們要在容量范圍內盡量買價值高的，有時候是買到恰好容量滿，這時候價值最大化。

直接dp遍歷找：

memset(d,0,sizeof(d));   /初始化為0.

for(int i=0;i<k;i++)   /共k個商品

for(int j=m;j>=w[i];j--)/d[j]表示容量為j時，背包的最大價值為d[j]

d[j]=max(d[j],d[j-w[i]]+v[i]); /進行比較選擇買和不買時造成的價值

cout<<d[m]<<endl;  /輸出容量為m時的最大價值

簡單的01背包模板就是上邊的，碰到類似的這類題改改就好了

這個模板是遞推型的，還有遞歸的，然而那個比較長，一般都用遞推的這個。

學姐給的練習題有些是先進行排序處理的，有些是需要你自己把題意轉化為01背包的問題，就如那個搶銀行概率問題。

練習題網址：

01背包練習題鏈接http://acm.hust.edu.cn/vjudge/contest/126172#overview