背包01扭曲 [英] knapsack 01 with twist

问题描述

我正在用Java做背包，我们只使用权重而没有价值。重量限制是1000.我们从键盘扫描了5个重量，我们使用。
扭曲的是，你可以实际超过1000，从壁橱到1000.所以在一个场景中我们有2个可能的权重990和1010，程序可以选择更高的一个。
扫描的数字永远不会高于1000。

I'm doing a Knapsack in Java where we only use weights no value. The weightlimit is 1000. We get 5 weights scanned from keyboard which we use. The twist is that you can actually go over 1000 aslong as its the closets to 1000. So in one scenario we have 2 possible weights 990 and 1010 and the program is suposed to pick the higher one. The scanned numbers can never be higher then 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，这样我就能理解他们所做的一些事情，即使我怀疑我将能够帮助编码。

I am really struggling with how I can get this done. Before you ask no its not homework im gonna be a project manager for a new group of people that consist of developers so im just trying to learn some java so that i understand a bit of what they do even tho i doubt i will be able to help with the coding.

推荐答案

我只会运行两次。

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

In first run find the "classic" solution with best weight less than 1000.

在第二次运行中，将最大值1000增加到最大值根据以前的解决方案允许的值。

In second run, increase the max value 1000 to the max possible value which is allowed based on previous solution.

不要担心它慢了两倍，将复杂性乘以常数不会改变复杂性，这是重要的事情在背包问题。

Dont worry about "it is two times slower", multiplying complexity by constant does not change the complexity, which is the important thing in knapsack problem.

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

If your code is working then you can probably count the best solution as this

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

或者您可以将其写为更清楚发生了什么（它与上面的那一行完全相同）

Or you can write it as this to be more clear what is happening (it does exactly the same as that one-line above)

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但是尽可能高。

---

EDIT : The solution above works for this condition select as big solution as possible, but it must not differ from 1000 more than "below 1000" best solution. The OP actually wants little different thing - the "limit" stays, but it should be the closest to the 1000 but as high as possible.

所以真正的解决方案是创建反向背包方法，它会找到最小值的解决方案BUT必须大于min变量。

So real solution would to create reversed knapsack method, which will find the solution with minimum value BUT must be bigger than "min" variable.

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
}

这篇关于背包01扭曲的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！