背包問題常見的有兩種刘陶，01背包問題和完全背包問題后裸，實現(xiàn)起來比較簡單，論證過程需要一定的數(shù)學推理知識骏啰，本文給出基本實現(xiàn)過程离斩，關(guān)于推理可以看一下網(wǎng)上的文章.
01背包問題
一個背包總?cè)萘繛閂银舱，現(xiàn)在有N個物品，第i個 物品體積為weight[i]跛梗，價值為value[i]寻馏，現(xiàn)在往背包里面裝東西，怎么裝能使背包的內(nèi)物品價值最大茄袖？每件物品只能選擇取或不取.
核心實現(xiàn)代碼:
<pre><code>` init(maxW:Int,value:[Int],weight:[Int]) {
maxWeight = maxW
values = value
weights = weight
let temp:[Int] = [Int].init(repeating: 0, count: maxWeight + 1)
calculate = [[Int]].init(repeating: temp, count: values.count)
}
func solveMaxValue()->Int {
for i in 1..<values.count { // 注意起始位置
for j in 1...maxWeight {
if weights[i] <= j {
calculate[i][j] = maxCompare(a: values[i] + calculate[i - 1][j - weights[i]], b: calculate[i-1][j])
} else {
calculate[i][j] = calculate[i - 1][j]
}
}
}
return calculate[values.count - 1][maxWeight]
}`</code></pre>
可以優(yōu)化為一維數(shù)組:
<pre><code>` func solveMaxValue2()->Int {
calculate2 = [Int].init(repeating: 0, count: maxWeight + 1)
for i in 1..<values.count {
for j in (1...maxWeight).reversed() {
if weights[i] <= j {
calculate2[j] = maxCompare(a: calculate2[j], b: (calculate2[j-weights[i]]+values[i]))
}
}
}
return calculate2[maxWeight]
}`</code></pre>
完全背包問題
一個背包總?cè)萘繛閂操软，現(xiàn)在有N個物品，第i個 物品體積為weight[i]宪祥，價值為value[i]聂薪，每個物品都有無限多件家乘，現(xiàn)在往背包里面裝東西，怎么裝能使背包的內(nèi)物品價值最大藏澳？
將01背包的第二種解法稍微調(diào)整即可:
<pre><code>` func solveMaxValue3()->Int {
calculate3 = [Int].init(repeating: 0, count: maxWeight + 1)
for i in 1..<values.count {
for j in 1...maxWeight {
if weights[i] <= j {
calculate3[j] = maxCompare(a: calculate3[j], b: (calculate3[j-weights[i]]+values[i]))
}
}
}
return calculate3[maxWeight]
}`</code></pre>
測試代碼:
<pre><code>`var values:[Int] = [0, 60, 100, 120] //為了理解第0個設(shè)置為0
var weights:[Int] = [0, 10, 20, 30]
values = [0,6,3,5,4,6]
weights = [0,2,2,6,5,4]
var max:Int = 10
var bag:Bag = Bag.init(maxW: max, value: values , weight: weights)
var maxValue = bag.solveMaxValue()
print("FlyElephant---01背包最大的值----(maxValue)")
var maxValue2 = bag.solveMaxValue2()
print("Fylephant---01背包最大值為---(maxValue2)")
var maxValue3 = bag.solveMaxValue3()
print("FlyElephant---完全背包最大值為---(maxValue3)")`</code></pre>
輸出結(jié)果:
參考資料
[0-1背包問題和部分背包(fractional knapsack)問題分析](http://shmilyaw-hotmail-com.iteye.com/blog/2009761](http://shmilyaw-hotmail-com.iteye.com/blog/2009761)
