我正在用 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，这样我就可以了解他们所做的一些事情，即使我怀疑我是否能够帮助编码。

最佳答案

我只会运行它两次。

在第一次运行中找到最佳权重小于 1000 的“经典”解决方案。

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

不要担心“它慢了两倍”，复杂度乘以常数并不会改变复杂度，这在背包问题中很重要。

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

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);

编辑:上面的解决方案适用于这种情况选择尽可能大的解决方案，但它不能与 1000 相差超过“低于 1000”的最佳解决方案。 OP 实际上想要一些不同的东西 - “限制”保留，但它应该最接近 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
}

关于java - 01 扭结背包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34082798/