算法惨不忍睹-背包

25 Sep 2017

看了道 leetcode 题目 https://leetcode.com/problems/ones-and-zeroes/description/

这其实是一道背包问题，使用背包的状态转移方程可以简单解决

轻轻松松试了下手，果断翻车了…

我发现并不是题目难，而是我一直没能真正理解背包算法为何会这样来设计？ 每次看到解答都会感觉反直觉，无法将直觉思路联系到这种解法，而网上的解题过程也大多由结果出发，没有掌握到 why

看题目时我的直觉是对每一个字符串判断需不需要，然后利用递归计算，算法如下。

def find_max_form(strs, m, n)
    str = strs.first # 当前字符串
    strs = strs[1..-1] # 剩余部分
    m1 = str&.count('0')
    n1 = str&.count('1')
    if str.nil?
        0
    elsif m1 > m || n1 > n
        # 放弃不满足条件的当前字符串
        find_max_form(strs, m, n)
    else
        # 选择构成当前的字符串时的数量 find_max_form(strs, m - m1, n - n1) + 1
        # 选择不构成当前字符串时的数量 find_max_form(strs, m, n)
        # 取大的作为真正解
        [find_max_form(strs, m - m1, n - n1) + 1, find_max_form(strs, m, n)].max
    end
end

很符合直觉的递归，结果是执行超时。

主要问题是其计算过程是自上而下，每次计算都会需要两个子递归运算的结果，最后递归的数量是 2 的 N(strs长度) 次方。

而正解巧妙的修复了这个问题，思路就是将自上而下的算法巧妙的转换为自下而上，让每个子计算的结果都被重复利用。

def find_max_form(strs, m, n)
    dp = Array.new(strs.size + 1){Array.new(m + 1){Array.new(n + 1)}}
    (strs.size + 1).times do |i|
        str = strs[i - 1]
        s0 = str.count('0')
        s1 = str.count('1')
        (m + 1).times do |j|
            (n + 1).times do |k|
                if i == 0
                    dp[i][j][k] = 0
                elsif j >= s0 && k >= s1
                    dp[i][j][k] = [dp[i - 1][j - s0][k - s1] + 1, dp[i - 1][j][k]].max
                else
                    dp[i][j][k] = dp[i - 1][j][k]
                end
            end
        end
    end
    dp[strs.size][m][n]
end

正解很聪明的将“第N个包”放不放的问题，转换为保存“前N个包的最优解”，从而让每个计算都可以利用之前的结果。