Question

动态规划的基本思想是什么？ 对于0-1背包问题, W=（1，2，3，4，5），V=(15, 20,25,30, 35, 18），背包承重量为C=6， 用动态规划求该0-1背包问题。

Answer 1

问：动态规划的基本思想是什么？ 对于0-1背包问题, W=（1，2，3，4，5），V=(15, 20, 25,30, 35, 18），背包承重量为C=6， 用动态规划求该0-1背包问题。

答：您好，很高兴为您解答。动态规划的基本思想是将一个复杂的问题，分解成一系列彼此相关的小问题，并尝试求解最优解。0-1背包问题: 用动态规划求解，可以利用数组m[i][j] 来表示，i表示前i件物品，j表示重量，m[i][j]表示有i件物品，重量不超过j时，能装下的最大价值。m[5][6]= max(m[4][5], m[4][6], m[4][5]-w[5]+v[5]), 求获得最大价值为38，可选择商品为1,2,4.