algorithm - 带有附加约束的 0/1 背包的最小化

Question

我和这里有同样的问题： Variation on knapsack - minimum total value exceeded 'W' with an added constraint。

细节：

我们有一组项目，每个项目 (i) 都有一个重量 (w_i) 和一个价值 (v_i) 和一个价格 (p_i)。我们必须选择这些项目的子组，以便：

• 最小化总总值

英石

1. 总重量至少为W。
2. 总总价格至多为P。

如果我们忽略最后一个约束，这相当于 0/1 背包问题，可以像上面链接的问题中提到的那样解决。加上最后一个约束，它仍然可以使用动态规划解决吗？

任何提示表示赞赏。

Answer 1

由于这是一个 NP 难题，您只需测试所有案例。

Answer 2

一个明显的解决方案是在您的动态编程状态下使用两个变量，W（当前重量）和 P（当前价格），这样 m[W][P] 可以为这两个参数提供最佳值。这将为您提供一个以 O(nP * 权重总和) 运行的算法。

您可能还需要考虑补充解决方案（反转 W 和 P，如阿米特的回答），具体取决于（权重总和）* P 或 W *（价格总和）是否更大。