动态规划中的背包问题描述

在动态规划中，背包问题是一个经典的优化问题，它可以分为0-1背包问题和完全背包问题两种类型。

1. 0-1背包问题：
假设有一个背包，它的容量为C。现在有n个物品，每个物品的重量分别为w1, w2, ..., wn，价值分别为v1, v2, ..., vn。要求选择一些物品放入背包中，使得在不超过背包容量的前提下，背包中物品的总价值最大化。
这里的0-1表示每个物品要么放入背包中，要么不放入。

2. 完全背包问题：
与0-1背包问题类似，但不同之处在于每个物品可以选择放入背包多次（数量无限），即每个物品的选择是一个无限的选择。

解决这两类背包问题的常用方法是使用动态规划。动态规划的基本思想是将原问题拆解成若干子问题，并通过求解子问题的最优解来求解原问题的最优解。

具体来说，对于0-1背包问题，可以使用一个二维数组dp[i][j]来表示前i个物品放入容量为j的背包中所能获得的最大价值。状态转移方程如下：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)
其中，dp[i-1][j]表示不选择第i个物品时的最大价值，dp[i-1][j-wi] + vi表示选择第i个物品时的最大价值。

对于完全背包问题，可以使用一个一维数组dp[j]来表示容量为j的背包所能获得的最大价值。状态转移方程如下：
dp[j] = max(dp[j], dp[j-wi] + vi)
其中，dp[j]表示不选择第i个物品时的最大价值，dp[j-wi] + vi表示选择第i个物品时的最大价值。