背包问题一个旅行者准备随身携带一个背包可以放入背包的物品有n种物品编号从1到n。第i件物品的重量和价值分别为w0和p装入背包的第种物品的数量为如果背包的最大重量制为M怎么选择放入背包的物品以使得背包的价值最大1若x; 01给出动态规划备忘录法求解该问题时问题最优解值及相应标记函数的递推方程2若x011给出动态规划备忘录法求解该问题时子问题最优解值及相应标记函数的递推方程3若x;eN给出动态规划备忘

1. 对于问题最优解值，可以定义一个二维数组dp[n+1][M+1]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])

其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品。

2. 对于子问题最优解值，可以定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])

其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品。

3. 对于子问题最优解值，可以定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品放入容量为j的背包中能达到的最大价值。递推方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])

其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-w[i]] + p[i]表示放入第i个物品