背包问题学习笔记(1)-基本的背包问题介绍

背包问题是动态规划中非常经典的问题。这里仅仅是一份学习笔记和简单的代码实现,更详细的介绍请见参考1和2。

01背包问题

题目

\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\)。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大。

基本思路

\(F[i,v]\)代表前\(i\)件物品放入容量为\(v\)的背包可以获得的最大价值。 01背包的状态转移方程为: \[F[i,v]=\max\{F[i-1][v],F[i-1][v-C_i]+W_i\}\] 将“前\(i\)件物品放入容量为\(v\)的背包”中这个子问题,只考虑地\(i\)件物品的策略(放或不放)。如果放入\(i\)物品,问题转为“前i-1件物品放入容量为\(v-C_i\) 的背包中“这个子问题的最大价值\(F[i-1,v-C_i]\)加上\(W_i\)。如果不放,问题转化为”前i-1件物品放入容量为\(v-C_i\) 的背包中“,价值为\(F[i-1,v]\)

代码是

Read More