给定一个背包容量C和一组n个物品,每个物品有两个属性:重量w和价值v。
要求从这组物品中选择若干放入背包中,使得在背包容量范围内能够获得最大的总价值。
其中,每个物品只能选择放入或不放入背包,不能进行分割。
具体而言,01背包问题可以定义为一个如下形式的问题:
给定一个背包容量C,一组物品A={a1, a2,...,an},其中每个物品ai有一个重量wi和一个价值vi,要求从这组物品中选择若干放入背包中(每个物品只能选择放入或不放入),使得在背包容量范围内(总重量不超过C)能够获得最大的总价值。
解决01背包问题的经典算法是动态规划算法,可以通过填充一个二维的dp数组来求解最优解,其中dp[i][j]表示在前i个物品中选择若干放入容量为j的背包中所能获得的最大总价值。
通过对dp数组的计算和填充,最终可以得到dp[n][C]即为所求的最大总价值。
01背包问题常用于解决一些资源限制下的优化问题,例如在有限的资源下选择最优的投资组合、购买物品以获得最大利益等场景。