以前在acm課上也講過一些關於背包的題，不過那些比較簡單，就是簡單的貪心問題，先排個序再處理就完了，而01背包，感覺就是比那個上了一個難度的問題，這個需要遍歷然後找其中合適的，簡單原理就是這樣。 例如：現在有容量為m的背包，還有重量為w，價值為v的k個不同的商品，問怎樣買才能使價值最大化？ 思路：如 ...
以前在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
密碼都是nefu待續……
