求解 0-1 背包问题

求解0-1背包问题可以使用动态规划法。首先，需要将问题抽象化，将物品的重量和价值表示为Wi和Vi，背包的最大承载重量表示为C。然后，建立模型，使用一个二维数组dp[i][j]表示前i个物品在背包承重为j时的最大价值。接下来，根据约束条件进行判断，如果将第i个物品放入背包时不超过背包的承重，则可以更新dp[i][j]的值为max(dp[i-1][j], dp[i-1][j-Wi]+Vi)，否则dp[i][j]的值等于dp[i-1][j]。通过填表的方式，不断更新dp数组的值，最终dp[n][C]即为背包问题的最优解。根据解组成，可以回溯得到具体的物品组合。