团子哒哒

题解

/ 注册

全部文章 / 题解（共2篇）

秒懂背包问题之完全背包

题目：已知一个背包最多能容纳物体的体积为V，现有n个物品第i个物品的体积为wi，第i个物品的重量为ci。且每种物品可以有无限个（0-1背包，一种物品只有一个）。求当前背包最多能装多大重量的物品。我们根据0-1背包问题进行改造，因为0-1背包每次只考虑拿一次的最大值，而这里我们可以取 [当前背包...

2021-04-12

4 1728

秒懂背包问题之0-1背包

1.分析： dp[i][j]表示：对于前i个物品，当前背包的容量为j时，这种情况下可以装下的最大价值是dp[i][j]。如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][j]应该等于dp[i-1][j]。你不装嘛，那就继承之前的结果。如果你把这第i个物品装入了背包，那么dp[i][j...

背包问题

2021-04-01

13 1617