有 n 个物品,每个有重量 w[i] 和价值 v[i],可以只拿一部分。求最大价值。
贪心策略:每次选「价值/重量」最高的物品。
与 01背包不同,可以拿一部分。装满为止。
部分背包用贪心可得最优解,01背包不行。