背包问题常见的有两种，01背包问题和完全背包问题，实现起来比较简单，论证过程需要一定的数学推理知识，本文给出基本实现过程，关于推理可以看一下网上的文章.

01背包问题

一个背包总容量为V，现在有N个物品，第i个 物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？每件物品只能选择取或不取.

bag.jpg

核心实现代码:
<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>

可以优化为一维数组:
<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>

完全背包问题

一个背包总容量为V，现在有N个物品，第i个 物品体积为weight[i]，价值为value[i]，每个物品都有无限多件，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
将01背包的第二种解法稍微调整即可:
<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个设置为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>
输出结果:

FlyElephant.png

参考资料
[0-1背包问题和部分背包(fractional knapsack)问题分析](http://shmilyaw-hotmail-com.iteye.com/blog/2009761](http://shmilyaw-hotmail-com.iteye.com/blog/2009761)