背包问题：动态规划求解最优解 - 详解及代码示例

"背包问题"是一个经典的算法问题，描述一个旅行者准备随身携带一个背包，可以放入背包的物品有n种，物品编号从1到n。第i件物品的重量和价值分别为w[i]>0和p[i]>0，装入背包的第i种物品的数量为x[i]。如果背包的最大重量制为M，怎么选择放入背包的物品以使得背包的价值最大？\n\n1) 若x[i] \u003c 0.1，给出动态规划(备忘录法)求解该问题时问题最优解值及相应标记函数的递推方程\n\n2) 若x[i] \u005b0,1\u005d，给出动态规划(备忘录法)求解该问题时子问题最优解值及相应标记函数的递推方程\n\n3) 若x[i] \u003c eN，给出动态规划(备忘录法) 求解该问题时子问题最优解值及相应标记函数的递推方程\n\n给出正确的解答步骤内容：\n\n1) 对于问题最优解值，可以定义一个二维数组dp[n+1][M+1]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：\n\ndp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])\n\n其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品。\n\n2) 对于子问题最优解值，可以定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：\n\ndp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])\n\n其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品。\n\n3) 对于子问题最优解值，可以定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：\n\ndp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])\n\n其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品。