背包问题

动态规划之背包问题

背包问题（Knapsack problem）是动态规划的经典问题。动态规划的基础是递归，和分治一样，都是假设子问题已经解决，由子问题的解组合计算得到父问题的解，类似裴波那契数列中的递推式如f(n) = f(n-1) + f(n-2)。但在递…