将背包问题简化为逆背包问题
Reducing knapsack problem to an inverse knapsack problem
1)假设我们有一个常见的 0-1 背包问题。给定一组 n 个项目，编号从 1 到 n，每个项目都有一个权重 w_i 和一个值 v_i，以及最大重量容量 W。这里我们需要 select 一些对象，以便最大化 v_i 的总和，使得 selected 对象的 w_i 的总和不会超过给定的 W 数。
maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W
2)现在假设我们有同样的问题，但我们需要 select 个对象，以便它们的值之和最小，并且它们的权重之和不能小于给定的数字.
minimize∑(v_i*x_i), such that ∑(w_i*x_i)≥ W.
知道第一个问题是NP完全的，我如何证明第二个问题具有相同的复杂性，换句话说也是NP完全的？
反背包是我的最爱之一。虽然我从未明确证明它是 NP 完全的，但我确实知道如何将问题重新表述为背包问题本身，这应该可以解决问题：
与其将对象添加到空包中，不如考虑选择要从已满包中取出的对象的问题。然后，由于权重的数量不能小于给定的数量，我们必须只删除总共（weight-minimum 个权重）的对象。
既然要使价格最小化，那么要移除的对象的价格就必须最大化。
我们剩下最初的背包问题，我们必须 select 一组物品（要删除），这样我们才能最大化它们的价格，并且它们的总重量不超过 weight-minimum 重量。 （最后，我们将没有删除的项目作为解决方案）
我们已经将问题改造为原来的背包问题，因此它也必须是NP-complete。
这种方法的美妙之处在于我个人不知道它是由什么NP完成的；我刚刚证明了逆背包和背包完全等价
关键思想似乎是交换价值和权重，并在第二个问题上使用二分查找来构造归约。
给定第一个公式的实例 I，其值 v_i 和权重 w_i，通过交换利润和权重构造第二个问题的实例。所有权重的总和（现在是利润）受限于
n * w_max
其中 w_max 是最大权重。这个数字本身是输入编码长度的指数；然而，我们可以使用二进制搜索来确定最大可获得的利润，这样就不会超过初始容量 W。这可以在
中完成
log( n * w_max )
iterations，一个在输入的编码大小中以多项式为界的数字，对第二个问题使用相同的算法调用次数。所描述的算法是从第一个问题到第二个问题的多项式简化。
Knowing that first problem is NP complete, how can I prove that second one has the same complexity, in other words is NP complete too?
如果你想证明问题B是NP-complete，你必须证明存在从A到B的多项式时间减少，其中A 已知是一个 NP-complete 问题。
从问题 A 到问题 B 的 polynomial-time 归约是一种使用多项式调用问题 B 的子例程来解决问题 A 的算法, 以及这些子程序调用之外的多项式时间。(source).
所以在你的情况下，你可以很容易地从背包问题到逆背包问题进行多项式时间减少。
这两个问题是等价的（找到一个的最优解立即解决另一个）。
令S为对象集合，M为S中对象的重量之和，W为背包的容量。
然后，我们有：
(i) 找到对象的子集，使得它们的重量之和不超过 W 并且它们的值之和最大
等同于
(ii) 找到一个对象子集，使得它们的权重之和至少为 M-W，并且它们的值之和最小。
那是因为如果S'是(i)的最优解，那么S\S'就是(ii)（和vice-versa）的最优解。
这是一个多项式时间缩减（O(1)调用子程序，多项式运算次数），所以倒背包确实是NP-complete.
1)假设我们有一个常见的 0-1 背包问题。给定一组 n 个项目，编号从 1 到 n，每个项目都有一个权重 w_i 和一个值 v_i，以及最大重量容量 W。这里我们需要 select 一些对象，以便最大化 v_i 的总和，使得 selected 对象的 w_i 的总和不会超过给定的 W 数。
maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W
2)现在假设我们有同样的问题，但我们需要 select 个对象，以便它们的值之和最小，并且它们的权重之和不能小于给定的数字.
minimize∑(v_i*x_i), such that ∑(w_i*x_i)≥ W.
知道第一个问题是NP完全的，我如何证明第二个问题具有相同的复杂性，换句话说也是NP完全的？
反背包是我的最爱之一。虽然我从未明确证明它是 NP 完全的，但我确实知道如何将问题重新表述为背包问题本身，这应该可以解决问题：
与其将对象添加到空包中，不如考虑选择要从已满包中取出的对象的问题。然后，由于权重的数量不能小于给定的数量，我们必须只删除总共（weight-minimum 个权重）的对象。
既然要使价格最小化，那么要移除的对象的价格就必须最大化。
我们剩下最初的背包问题，我们必须 select 一组物品（要删除），这样我们才能最大化它们的价格，并且它们的总重量不超过 weight-minimum 重量。 （最后，我们将没有删除的项目作为解决方案）
我们已经将问题改造为原来的背包问题，因此它也必须是NP-complete。
这种方法的美妙之处在于我个人不知道它是由什么NP完成的；我刚刚证明了逆背包和背包完全等价
关键思想似乎是交换价值和权重，并在第二个问题上使用二分查找来构造归约。
给定第一个公式的实例 I，其值 v_i 和权重 w_i，通过交换利润和权重构造第二个问题的实例。所有权重的总和（现在是利润）受限于
n * w_max
其中 w_max 是最大权重。这个数字本身是输入编码长度的指数；然而，我们可以使用二进制搜索来确定最大可获得的利润，这样就不会超过初始容量 W。这可以在
log( n * w_max )
iterations，一个在输入的编码大小中以多项式为界的数字，对第二个问题使用相同的算法调用次数。所描述的算法是从第一个问题到第二个问题的多项式简化。
Knowing that first problem is NP complete, how can I prove that second one has the same complexity, in other words is NP complete too?
如果你想证明问题B是NP-complete，你必须证明存在从A到B的多项式时间减少，其中A 已知是一个 NP-complete 问题。
从问题 A 到问题 B 的 polynomial-time 归约是一种使用多项式调用问题 B 的子例程来解决问题 A 的算法, 以及这些子程序调用之外的多项式时间。(source).
所以在你的情况下，你可以很容易地从背包问题到逆背包问题进行多项式时间减少。
这两个问题是等价的（找到一个的最优解立即解决另一个）。
令S为对象集合，M为S中对象的重量之和，W为背包的容量。
然后，我们有：
(i)找到对象的子集，使得它们的重量之和不超过W并且它们的值之和最大
等同于
(ii)找到一个对象子集，使得它们的权重之和至少为M-W，并且它们的值之和最小。
那是因为如果S'是(i)的最优解，那么S\S'就是(ii)（和vice-versa）的最优解。
这是一个多项式时间缩减（O(1)调用子程序，多项式运算次数），所以倒背包确实是NP-complete.