思路:
乍一看像一个普通的01背包, 但是每个物品的”价值”是与时间有关的, 所以不是个单纯的01背包.
同时考虑物品的顺序对结果有影响, 所以不能只用dp解决.
考虑物品$i$与物品$j$, 假设已经花费时间$t$, 则先取$i$后取$j$增加的价值为:
先取$j$后取$i$为:
若$v_1 > v_2$, 则有:
也即, 对于两个物品的序偶$< i, j >$, 如果满足上述不等式, 则优先考虑$i$更优.
所以对物品按上述方式排序后, 按此排序进行dp就解决了物品考虑顺序的问题(按此顺序比其他顺序一定更优), 剩下的就是01背包了.
代码:
1 |
|