版权所有,转载请注明出处!
动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。
比如01背包问题。
/* 一个旅行者有一个最多能用M公斤的背包,现在有N件物品,
它们的重量分别是W1,W2,...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。
输入格式:
M,N
W1,P1
W2,P2
......
输出格式:
X
*/
因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进......
阅读全文