0-1背包问题

0-1背包问题是指有一个固定容量的背包，若干个物品，每个物品的重量和价值不同。要求在不超过背包容量的前提下，选择一定数量的物品放入背包中，使得放入背包中物品的总价值最大。

这是一个经典的动态规划问题，可以用动态规划算法求解。具体方法是建立一个二维数组dp，其中dp[i][j]表示前i个物品放入一个容量为j的背包中所能获得的最大价值。则状态转移方程为：

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

其中w[i]和v[i]分别表示第i个物品的重量和价值，i从1到n，j从1到W，n为物品数量，W为背包容量。最终的最大价值即为dp[n][W]。

注意，由于每个物品只能选一次，因此在转移时需要判断是否可以放入当前物品，即若j<w[i]，则不能放入当前物品，此时dp[i][j]的值等于dp[i-1][j]。