首页 > 代码库 > 0 1背包问题 (内有题目列表)

0 1背包问题 (内有题目列表)

问题描述:一个背包可承重W,现有n件东西,东西 i 的价值为 vi,重量为wi。现在从这n件东西中拿出几件装到背包中,问可获得的最大价值?

举例:W = 3, n = 3;

东西的价值

vi  wi
3
  4

4  5

5  6

DP的解法:

先从递归的角度理解这个问题,然后在贴上非递归的模板。

现在为东西编号:0 1 2 3 …n-1;我们先从n-1开始(其实从哪一端开始都无所谓,不要在意这些细节),我其实不觉得这个算法属于DP的,不管这个了。

Make(i,j) = max{Make(i-1,j-w[i])+v[i](取编号为 i 的东西),Make(i-1,j)(没有取编号为i的产品)}

0 1背包问题 (内有题目列表)