根据维基百科,背包问题(Knapsack problem)是一种组合优化的NP完全(NP-Complete,NPC)问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的,但是利用动态规划,我们可以以伪多项式时间复杂度求解背包问题。 01背包问题定一个背包,容量为V。一共有n件物品,第i件物品的价值为w[i],体积为v[i]。求背包中能装入物品的价值总和最大为多少。使用动态规划求解。设置dp[i][j]表示前i件物品,在总体积不超过j的情况下,价值总和最大为dp[i][j]。则有dp[...