knapsack 01 with twist

问题:

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];
    }
}

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.

回答1:

I would just run it twice.

In first run find the "classic" solution with best weight less than 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);

---

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.

---

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
}

回答2:

Verbatim from Wikipedia — 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.

After computing the values of Q, we may loop through them, and take the true value which is closest to the limit.

As for the value of S, we need to take the sum of the weights given to us.

回答3:

The classical knapsack problem is discussed in a Wikipedia article; the dynamic programming formulation for the classical problem can be adapted to the following problem.

Given weights w_1,...,w_n and a target capacity W, find a subset of the items for which the total weight is minimal, but larger than W.

To avoid pathological cases, we assume that the sum of the weights is largert than W, otherwise there is no solution. Let W_MAX denote the sum of all weights.

For the dynamic programming formulation, let

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

denote the minimum weight larger than W attainable by discarding weights from 0,...,i with total weight exactly j.

We obtain

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

and get the recurrence relation

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
             }

and evaluation can be implemented by iterating i=0,...,n and j=0,...,W_MAX; accedd to m outside of these bounds must be assumed to yield W_MAX. Similar to the classical knapsack problem, the actual set of items to discard can be found by backtracking.

Finally, the given instance can be optimized twice; first with the algorithm above, then with the classical knapsack algorithm.

回答4:

I would evaluate this problem first as a classical knapsack problem taking
value[i] = weight[i] ;
, where i is the i'th item and maximum weight to be the given max_wt (1000 kg) and item[] be an array containing the items in ascending order of their weights .

Let the answer of this problem be x , say 990 kg , now i would calculate the difference 'd' ,
d = max_wt - x ;
iterate over item[] till item[i] exceeds d :
int i = 0 ; while(item[i] < d ) i++; ,lastly add the first item that exceeds 'd' to the answer you got through the classical knapsack problem :
answer = dp[n-1][w-1] + item[i] \\dp[n-1][w-1] is the answer of the classical \\knapsack problem