01 扭结背包

Question

我在 Java 做一个背包，我们只使用重量没有价值。权重限制为 1000。我们从使用的键盘扫描了 5 个权重。不同之处在于，只要壁橱达到 1000，您实际上就可以超过 1000。因此，在一种情况下，我们有 2 个可能的权重 990 和 1010，程序应该选择较高的一个。扫描的数字不能大于1000

package kapsackidone;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
public class Kapsack {

public static void main(String[] args) throws Exception {
    BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

    int [] wt=new int[5];
    int W = 1000;

    System.out.println("Enter Weight 5 weights");
    for(int i=0; i<5; i++)
    {
        wt[i]=Integer.parseInt(reader.readLine());
    }   
    System.out.println(knapsack(wt, W));
}

public static int knapsack(int wt[], int W) {
    int N = wt.length;
    int[][] V = new int[N + 1][W + 1];

    for (int col = 0; col <= W; col++) {
        V[0][col] = 0;
    }


    for (int row = 0; row <= N; row++) {
        V[row][0] = 0;
    }

    for (int item=1;item<=N;item++){

    for (int weight=1;weight<=W;weight++){
        if(wt[item-1] > weight)
        {
            V[item][weight] = V[item-1][weight];
        }
        else if((weight - V[item-1][weight]) < (weight - (V[item-1][weight - wt[item-1]] + wt[item-1])))
        {
            V[item][weight] = V[item-1][weight];
        }
        else
        {
            V[item][weight] = V[item-1][weight - wt[item-1]] + wt[item-1];
        }
    }
    }

    return V[N][W];
    }
}

我真的很苦恼如何才能完成这项工作。在你问不之前，这不是家庭作业，我将成为一个由开发人员组成的新团队的项目经理，所以我只是想学习一些 java 以便我了解他们所做的一些事情，即使我怀疑我将能够帮助编码。

Answer 1

我会运行两次。

首先运行找到最佳权重小于1000的"classic"解。

在第二个运行中，将最大值 1000 增加到基于先前解决方案所允许的最大可能值。

不用担心"it is two times slower"，复杂度乘以常数不会改变复杂度，这在背包问题中很重要。

如果您的代码可以正常工作，那么您可能可以算出最佳解决方案

System.out.println(knapsack(wt,2*W - knapsack(wt, W));

或者你可以这样写，这样更清楚发生了什么（它和上面那一行完全一样）

int bestClassicSolution = knapsack(wt, W);
int differenceAgainstMaxWeight = W - bestClassicSolution;
int newMaxWeight = W + differenceAgainstMaxWeight;
int bestSolution = knapsack(wt, newMaxWeight);
System.out.println(bestSolution);

编辑：上面的解决方案适用于这种情况 select as big solution as possible, but it must not differ from 1000 more than "below 1000" best solution。 OP 实际上想要一些不同的东西 - "limit" 保留，但它应该最接近 1000 但尽可能高。

所以真正的解决方案将创建反向背包方法，它将找到具有最小值但必须大于 "min" 变量的解决方案。

public static void main(String[] args) throws Exception {
    BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

    int [] wt=new int[5];
    int W = 1000;

    System.out.println("Enter Weight 5 weights");
    for(int i=0; i<5; i++)
    {
        wt[i]=Integer.parseInt(reader.readLine());
    }   
    int bestClassicSolution = knapsack(wt, W);
    int differenceAgainstMaxWeight = W - bestClassicSolution;
    int newMaxWeight = W + differenceAgainstMaxWeight;
    int bestMaxSolution = reversedKnapsack(wt, newMaxWeight, W);
    int differenceAgainstWeightAboveW = W - bestMaxSolution;

    if (differenceAgainstWeightAboveW <= differenceAgainstMaxWeight){
        System.out.println(bestMaxSolution);
    } else {
        System.out.println(bestClassicSolution);
    }
}

public static int reversedKnapsack(int wt[], int W, int min) {
    //similar to knapsack method, but the solution must be as small as possible and must be bigger than min variable
}

Answer 2

来自维基百科的逐字记录 — Subset sum problem.

The problem can be solved in pseudo-polynomial time using dynamic programming. Suppose the sequence is

x1, ..., xN and we wish to determine if there is a nonempty subset which sums to zero. Define the boolean-valued function Q(i, s) to be the value (true or false) if

"there is a nonempty subset of x1, ..., xi which sums to s". Thus, the solution to the problem "Given a set of integers, is there a non-empty subset whose sum is zero?" is the value of Q(N, 0).

Let A be the sum of the negative values and B the sum of the positive values. Clearly, Q(i, s) = false, if s < A or s > B. So these values do not need to be stored or computed.

Create an array to hold the values Q(i, s) for 1 ≤ i ≤ N and A ≤ s ≤ B.

The array can now be filled in using a simple recursion. Initially, for A ≤ s ≤ B, set

Q(1, s) := (x1 == s) where == is a boolean function that returns true if x1 is equal to s, false otherwise.

Then, for i = 2, …, N, set

Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi), for A ≤ s ≤ B.

计算出Q的值后，我们可以循环遍历它们，并取最接近极限的真值。

关于S的取值，我们需要对给定的权重求和。

Answer 3

在Wikipedia article中讨论了经典的背包问题；经典问题的动态规划公式可以适用于以下问题。

给定权重 w_1,...,w_n 和目标容量 W，找到总重量最小但大于 W 的项目子集。

为避免病态情况，我们假设权重之和大于W，否则无解。让 W_MAX 表示所有权重的总和。

对于动态规划公式，令

m[i,j] for each i in 0,...,n and j in 0,...,W_MAX

表示通过丢弃 0,...,i 中的权重且总权重恰好 j.

可获得的大于 W 的最小权重

我们得到

m[0,j] = W_MAX for each j in 0,...n

并得到递归关系

m[i,j] = min {
               m[i-1, i       ],       // corresponds to keeping weight i
               m[i-1, j - w[i]] - w[i] // corresponds to discarding weight i
             }

和评估可以通过迭代i=0,...,n和j=0,...,W_MAX来实现；必须假定在这些界限之外加入 m 会产生 W_MAX。类似于经典的背包问题，实际要丢弃的物品集可以通过 backtracking.

找到

最后，给定的实例可以优化两次；先用上面的算法，再用经典的背包算法。

Answer 4

我首先将这个问题作为一个经典的背包问题来评估
value[i] = weight[i] ;
，其中 i 是第 i 个项目，最大重量是给定的 max_wt (1000 kg) 和 item[] 是一个数组，其中包含按重量升序排列的项目。

让这个问题的答案是 x ，比如 990 kg ，现在我会计算差异 'd' ,
d = max_wt - x ;
迭代 item[] 直到 item[i] 超过 d :
int i = 0 ; while(item[i] < d ) i++; ,最后把第一个超过'd'的项目加到你通过经典背包问题得到的答案中:
answer = dp[n-1][w-1] + item[i] \dp[n-1][w-1] is the answer of the classical \knapsack problem

01 扭结背包

knapsack 01 with twist

java

knapsack-problem