回溯算法：0-1背包问题

/**
 * 0-1背包问题
 */
class Knapsack {

    private lateinit var itemWeightArr: Array<Int>
    private lateinit var itemValueArr: Array<Int>
    private var totalWeight: Int = 0;
    
    private var maxValue = 0
    private var maxSelectedIndexStr = ""

    /**
     * 计算背包问题
     *
     * @param itemWeightArr 物品的重量
     * @param itemValueArr 每个物品的价值
     * @param totalWeight 背包能够容纳的总重量
     */
    fun calc(itemWeightArr: Array<Int>, itemValueArr: Array<Int>, totalWeight: Int) {
        this.itemWeightArr = itemWeightArr
        this.itemValueArr = itemValueArr
        this.totalWeight = totalWeight
        this.maxValue = 0
        this.maxSelectedIndexStr = ""        
        calcRecursive(0, 0, 0, "")
    }

    /**
     * 递归计算
     *
     * @param index 表示开始放第几个物品
     * @param currWeight 表示当前背包的物品总量
     * @param currValue 表示当前背包的物品总价值
     */
    private fun calcRecursive(index: Int, currWeight: Int, currValue: Int, currSelectedStr: String) {
        if (index >= itemWeightArr.size || currWeight == this.totalWeight) {
            if (currValue > this.maxValue) {
                this.maxValue = currValue
                this.maxSelectedIndexStr = currSelectedStr
            }
            return
        }
        //当前物品不放
        calcRecursive(index + 1, currWeight, currValue, currSelectedStr)
        //当前物品放进去
        if (itemWeightArr[index] + currWeight <= this.totalWeight) {
            calcRecursive(index + 1, itemWeightArr[index] + currWeight,
                itemValueArr[index] + currValue, "${currSelectedStr}${if (currSelectedStr.isEmpty()) "" else ","}${index}")
        }
    }

    fun getMaxValue(): Int {
        println(this.maxSelectedIndexStr)
        return this.maxValue
    }
}

测试验证：

    var items: Array<Int> = arrayOf(2, 2, 4, 6, 2)
    var values: Array<Int> = arrayOf(3, 4, 8, 9, 9)
    val knapsack = Knapsack()
    knapsack.calc(items, values, 8)
    println("最大价值：${knapsack.getMaxValue()}")

结果为：

1,2,4
最大价值：21

即选择第 2、3、5 个物品，不仅总重量没有超过背包容量，并且总的价值最大为：21