Description
有一个体积为 v 的背包,一共有 n 个物品,每个物品的体积为 ti,价值为 pi 。现要从中取若干物品放入背包,使背包中物品的价值和最大。
(1≤n≤105,1≤v≤109,1≤ti≤2,1≤pi≤104)
Source
Solution
发现物品的体积只有 2 种,分别是 1 和 2 。我们可以根据体积把它们分成两类。
假如所有物品都是同一类的,一个很显然的贪心是选价值较大的更优,所以对于每一类我们将物品按价值从大到小排序。
考虑枚举体积为 1 的物品放多少个,剩下的空间全部放体积为 2 的物品,判断是否能够更新答案即可。时间复杂度为排序的复杂度 O(nlogn) 。
Code
1 |
|
Be the first person to leave a comment!