我试图通过JAVA用Choco Solver实现一个多维背包问题。我的想法是在两个背包中分配3件物品。我的物品有一个重量和背包的极限: int[] itemWeight = {2,2,2};int[] knapsackLimit = {4,4};我使用Choco Solver编写了这个问题:
Model model = new Model("Kn
1)假设我们有一个共同的0-1背包问题。给定一组从1到n的项目,每个项目都有一个权重w_i和一个值v_i,以及一个最大的权重容量W。maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W
2)现在假设我们有同样的问题,但是我们需要选择对象,使它们的值和最小,并且它们的权重之和不能小于给定的数目。如果知道第一个问题是NP完全的,那么如何证明第二个问题具有相同的复杂性,换句话说,NP也是完全的?