关于同时最小化的NP硬度和加权子集最大化的证明

Question

我正在研究定义为以下的问题

给定一组 $ n $ 元素，称为 $ r \ subseteq \ mathbb {n} \ times \ mathbb { n} $ 和数字 $ z，g \ in \ mathbb {n} $ ，其中 $ z $ 是我们的资源和 $ g $ 是我们必要的最小奖励的衡量标准，有没有set $ r '\ subseteq r $ ，使 $ \ sum _ {（z，g）\ in r'} z \ leq z $ 和 $ \ sum _ {（z，g）\ in r'} g \ geq g $ ？

我想展示它的np完整性，并显示它已经存在于np。我正在努力与NP硬度斗争。我已知的NP难题是SAT，3SAT，分区，子集和箱包装。

我的斗争似乎主要是我们现在必须平衡两种不同的价值，成本和奖励。在我提到的任何设置相关问题中，这不是这种情况，我无法想到如何在SAT或3SAT中建模这一点。我在这里遗漏了什么？我如何只使用这些给定的问题显示NP硬度，并在此问题的情况下，使用这些问题的NP完整性？

Answer 1

这听起来像背包问题其中

• $ z $ 是每个项目的权重
• $ z $ 是背包的容量，
• $ g $ 项目的值和
• $ g $ 要实现的值。

问题是 np-complete ，但使用动态编程，在伪多项式时间 $ o（n \ Cdot w）$ 其中 $ w=max _ {r}（g）$ 。

您可以证明knapsack问题是通过从子集和问题。实际上，子集总和是背包的特殊情况，其中 $ z= g $ ;每个问题的“权重”与其“值”相同。