algorithm - 01 有m个物品限制的背包问题

Question

有一个容量为C的背包，有n个项目可供选择，每个项目只有一个，并且它们的大小和值分别是ci和vi（i=1,2,...,n），如何选择物品从物品中最多装载m个物品的条件下，使背包中的总价值最大化？谁能告诉我这个问题的具体思路，或者有什么代码可以看的吗？THS

标签： algorithmdynamic-programming

Answer 1

您应该定义以下函数 f(i,j,k)，它可以通过从最大容量为 j 的前 i 个项目 (1,2..i) 中精确选择 k 个项目来为您提供可以得到的最大值。

根据我们的定义，转换将是：

f(i , j , k) = max( t1 , t2 )

t1 = f(i-i , j , k) // here we did not pick the i-th item

t2 = vi + f(i-1 , j - ci , k-1)// here we picked the i-th item

您的问题的结果将是 max( f(n,C,i) ) 其中 i=1,2...n