Twist Backpack 01

Question

I do Knapsack in Java, where we use only weights. Weightlimit - 1000. We get 5 weights scanned from the keyboard that we use. The twist is that you can actually move more than 1000, since its cabinets are up to 1000. Thus, in one scenario, we have 2 possible weights 990 and 1010, and the program is selected to choose a higher one. Scanned numbers can never be higher than 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 fighting over how I can do this. Before you ask if this will not be homework, I will become a project manager for a new group of people who are developers, so I'm just trying to learn some Java, so that I understand what they are doing, I even doubt that I can help in coding.

Answer 1

I would just run it twice.

In the first run, find a “classic” solution with a better weight of less than 1000.

In the second run, increase the maximum value of 1000 to the maximum possible value that is allowed based on the previous solution.

Do not worry about the fact that "it is twice as slow", multiplying complexity by a constant, does not change the complexity, which is important in the knapsack problem.

---

If your code works, you can probably consider a better solution like this

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

Or you can write it like this to make it clearer what is happening (it does the same thing as 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 . OP actually wants a little different - the "limit" remains, but it should be closest to 1000, but as high as possible.

---

Thus, a real solution could create a backpack method that finds a solution with a minimum BUT value that should be greater than the 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 } 

Answer 2

Wikipedia Verbatim - Subset Sum Problem .

The problem can be solved in pseudopolynomial time using dynamic programming. Assume the sequence

x1, ..., xN and we want to determine if there is a nonempty subset that sums with zero. Define the logical function Q(i, s) as a value (true or false) if

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

Let A be the sum of negative values, and B be the sum of positive values. It is clear that Q (i, s) = false if s <A or s> B. Therefore, these values ​​do not need to be stored or calculated.

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

Now the array can be filled using simple recursion. Initially, for A ≤ s ≤ B, set

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

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 calculating the Q values, we can skip 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.

Answer 3

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

Given the weight w_1,...,w_n and the target capacity W find the subset of elements for which the total weight is minimal but greater than W

To avoid pathological cases, suppose that the sum of the weights is greater than W , otherwise there is no solution. Denote by W_MAX sum of all weights.

To formulate dynamic programming, let

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

denotes the minimum weight exceeding W achieved by dropping weights from 0,...,i with a total weight of exactly j .

We get

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

and get the recurrence ratio

 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 the estimate can be performed by repeating i=0,...,n and j=0,...,W_MAX ; take m outside these boundaries to get W_MAX . Like the classic knapsack problem, the actual set of elements to drop can be found backtracking .

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

Answer 4

I would first rate this problem as a classic backpack problem, taking value[i] = weight[i] ;
, where i is the i-th element, and the maximum weight is the specified max_wt (1000 kg) and item [] is an array containing the elements in ascending order of their weights.

Let the answer to this problem be x, say, 990 kg, now I would calculate the difference "d",
d = max_wt - x ;
iteration over the element [] to the point [i] exceeds d:
int i = 0 ; while(item[i] < d ) i++; finally add the first element that exceeds "d" to the answer you got on the classic backpack problem:
answer = dp[n-1][w-1] + item[i] \\dp[n-1][w-1] is the answer of the classical \\knapsack problem