建站
咨詢
售后
建站咨詢
新聞中心
[[420643]]
01故事起源
有一個(gè)容量有限的背包，容量為w，以及m個(gè)待選擇的物品，每個(gè)只有一件。每個(gè)物品有一定的重量和價(jià)值，那么選擇哪些物品放入背包，可使選擇的物品總價(jià)值最大呢?
為渝中等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及渝中網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、渝中網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！
02問題解析
如果背包沒有容量限制，那肯定是把所有的物品都放入背包可使價(jià)值最大。
但現(xiàn)在背包比較小，只能選擇部分裝進(jìn)背包，比如只能放一個(gè)，那就把鉆石裝進(jìn)去。
很容易可以想到，盡量放重量小且單價(jià)高的物品，但怎么對問題進(jìn)行一個(gè)嚴(yán)謹(jǐn)?shù)慕Ｄ兀^續(xù)往下分析。
03分析
背包有一個(gè)固定的容量，容量是1kg，或者2kg，或者3kg，其實(shí)具體的數(shù)量對問題的本質(zhì)沒有影響。
對于物品來說，也就分兩種情況，要么放入背包，要么不放。
有m個(gè)物品，那總共就有2^m種選擇方式，很明顯這個(gè)數(shù)量很大，所以也不可能直接把所有的選擇方式枚舉出來。
04小問題過度大問題
假設(shè)背包容量為1kg，那可裝入的最大價(jià)值就是將手表裝入，其他的也裝不下。
如果有一個(gè)更大的背包，它的容量可以看成是2個(gè)小容量的背包的總和。
但它能裝入的價(jià)值卻不能簡單的直接分解為2個(gè)小背包，因?yàn)槲锲分挥幸粋€(gè)，這會(huì)導(dǎo)致物品重復(fù)。
所以對物品也再進(jìn)行一次劃分，m個(gè)物品可以分解為m1+m2個(gè)，同時(shí)背包容量也分解為w1+w2。
再看上面左右兩邊，和原來的問題還是一樣的，本質(zhì)不變，只是變成了數(shù)據(jù)規(guī)模更小的一個(gè)子問題。如果有了子問題的答案，那是不是就可以組合成更大規(guī)模的答案了呢?
我猜這里肯定有同學(xué)會(huì)說，這樣分解的小問題一定能得到最終大問題的最優(yōu)解嗎?我們來嘗試證明一下。
05逆向思維
假設(shè)下面就是最終的最優(yōu)解選擇的物品。
如果從某個(gè)位置砍一刀分開，保證w1和w2能裝下自己這邊的最終選擇物品，那最優(yōu)解也就被分成了兩個(gè)小規(guī)模問題的最優(yōu)解。這也說明如果枚舉了所有小規(guī)模最優(yōu)解的組合方式，也一定能得到大規(guī)模的最優(yōu)解。
06算法建模
根據(jù)上面的分析，現(xiàn)在問題就變得簡單了，直接按物品和重量拆分小問題，通過小問題遞推出大問題就行了。
設(shè)f[i][j]表示前i個(gè)物品背包容量為j時(shí)，能選擇的最大價(jià)值。w[i]表示第i個(gè)物品的重量，v[i]表示第i個(gè)物品的價(jià)值。
- 裝不下第i個(gè)物品，則f[i][j]=f[i-1][j]
- 能裝下第i個(gè)物品，則f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])
那為什么只需要從前i-1個(gè)物品遞推就行了呢，因?yàn)橹恍枰幸环N情況能得到最優(yōu)解就夠了，并不需要把前面的所有劃分都枚舉出來。這其實(shí)就相當(dāng)于把i個(gè)物品劃分成i-1個(gè)物品和1個(gè)物品時(shí)的情況。前面的子問題也已經(jīng)包含在當(dāng)前的解中了。
代碼實(shí)現(xiàn)
- int f[101][1001], w[101], v[101];
- int n, m;
- int main() {
- cin >> m >> n;
- for (int i = 1; i <= m; ++i) {
- cin >> w[i] >> v[i];
- }
- f[0][0] = 0;
- for (int i = 1; i <= m; ++i) {
- for (int j = 0; j <= n; ++j) {
- f[i][j] = f[i - 1][j];
- if (j >= w[i]) {
- f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
- }
- }
- }
- cout << f[m][n] << endl;
- return 0;
- }
07總結(jié)
背包在動(dòng)態(tài)規(guī)劃中是一個(gè)非常重要的系列，涉及的類型和變種也非常的多，今天講的01背包是最基本的一種，不過真正理解了01背包，對后續(xù)其它的背包也才能更好的掌握。
本文原創(chuàng)作者：小K，一個(gè)思維獨(dú)特的寫手。
當(dāng)前題目：你覺得背包真的很簡單嗎？
本文地址：http://www.5511xx.com/article/ccocgge.html
