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背包问题，可以使用动态规划算法求得最优解，建立如下递归公式：f(i,j)=max{f(i-1,j),f(i-1,j-w(i))+v(i)}，其中f(i,j)表示前i件物品放入容量为j的背包中的最优解；w(i)、v(i)表示第i件物品的重量和价值。依据该公式，发现在背包容量为6的情况下，装入物品的最大价值是38。