在上一篇《9.動(dòng)態(tài)規(guī)劃（2）——子集和問(wèn)題》中，談到了什么是子集和問(wèn)題，以及實(shí)現(xiàn)。背包問(wèn)題實(shí)際也是子集和問(wèn)題的一種，不過(guò)背包問(wèn)題不是“判斷問(wèn)題”而是一個(gè)“最優(yōu)問(wèn)題”。而背包問(wèn)題實(shí)際上又分為“0-1背包”，“完全背包”，本文對(duì)“0-1背包”進(jìn)行講解。
問(wèn)題：有n個(gè)物品，每個(gè)物品的重量為weigh[i]，每個(gè)物品所對(duì)應(yīng)的價(jià)值為price[i]，現(xiàn)在有一個(gè)背包，背包所能承受的重量為W，問(wèn)背包能裝下的物品總價(jià)值最大是多少？
定義s[i, j]表示前i個(gè)物品的總價(jià)值，j為背包的承重量。當(dāng)j = W或者最接近于W且小于W時(shí)，此時(shí)就是問(wèn)題的解。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式