0-1 Knapsack Algorithm

Question

Is the following problem 0-1 Backpack solvable:

• 'float' positive values ​​and
• "float" (may be positive or negative)
• 'float' backpack capacity> 0

I have an average of <10 elements, so I'm thinking about using brute force. However, I was wondering if there is a better way to do this.

Answer 1

This is a relatively simple binary program.

I offer brute force with cropping. If at any time you exceed the permissible weight, you will not need to use combinations of additional items, you can discard the entire tree.

Oh, do you have negative weights? Always include all negative weights, then proceed as described above for positive weights. Or are negative values ​​negative?

Include all negative weights with a positive value. Exclude all items with a positive weight and a negative value.

For negative weights with a negative value, subtract their weight (increasing the capacity for the satchel) and use a pseudo-element that does not accept this item. The pseudo-element will have a positive weight and value. Perform brute force with cropping.

class Knapsack { double bestValue; bool[] bestItems; double[] itemValues; double[] itemWeights; double weightLimit; void SolveRecursive( bool[] chosen, int depth, double currentWeight, double currentValue, double remainingValue ) { if (currentWeight > weightLimit) return; if (currentValue + remainingValue < bestValue) return; if (depth == chosen.Length) { bestValue = currentValue; System.Array.Copy(chosen, bestItems, chosen.Length); return; } remainingValue -= itemValues[depth]; chosen[depth] = false; SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue); chosen[depth] = true; currentWeight += itemWeights[depth]; currentValue += itemValues[depth]; SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue); } public bool[] Solve() { var chosen = new bool[itemWeights.Length]; bestItems = new bool[itemWeights.Length]; bestValue = 0.0; double totalValue = 0.0; foreach (var v in itemValues) totalValue += v; SolveRecursive(chosen, 0, 0.0, 0.0, totalValue); return bestItems; } } 

Answer 2

Yes, by brute force. This is an NP-Complete problem, but it does not matter because you will have less than 10 items. Forced coercion will not be problematic.

  var size = 10; var capacity = 0; var permutations = 1024; var repeat = 10000; // Generate items float[] items = new float[size]; float[] weights = new float[size]; Random rand = new Random(); for (int i = 0; i < size; i++) { items[i] = (float)rand.NextDouble(); weights[i] = (float)rand.NextDouble(); if (rand.Next(2) == 1) { weights[i] *= -1; } } // solution int bestPosition= -1; Stopwatch sw = new Stopwatch(); sw.Start(); // for perf testing //for (int r = 0; r < repeat; r++) { var bestValue = 0d; // solve for (int i = 0; i < permutations; i++) { var total = 0d; var weight = 0d; for (int j = 0; j < size; j++) { if (((i >> j) & 1) == 1) { total += items[j]; weight += weights[j]; } } if (weight <= capacity && total > bestValue) { bestPosition = i; bestValue = total; } } } sw.Stop(); sw.Elapsed.ToString(); 

Answer 3

If you can only have positive values, then each item with a negative weight should go in.

Then, I think, you could calculate the value / weight ratio and roughly force the rest of the combinations based on this order, as soon as you get the one that suits you, you can skip the rest.

The problem may be that sorting and sorting is actually more expensive than just doing all the calculations.

Obviously, there will be another breakeven point based on the size and distribution of the set.

Answer 4

 public class KnapSackSolver { public static void main(String[] args) { int N = Integer.parseInt(args[0]); // number of items int W = Integer.parseInt(args[1]); // maximum weight of knapsack int[] profit = new int[N + 1]; int[] weight = new int[N + 1]; // generate random instance, items 1..N for (int n = 1; n <= N; n++) { profit[n] = (int) (Math.random() * 1000); weight[n] = (int) (Math.random() * W); } // opt[n][w] = max profit of packing items 1..n with weight limit w // sol[n][w] = does opt solution to pack items 1..n with weight limit w // include item n? int[][] opt = new int[N + 1][W + 1]; boolean[][] sol = new boolean[N + 1][W + 1]; for (int n = 1; n <= N; n++) { for (int w = 1; w <= W; w++) { // don't take item n int option1 = opt[n - 1][w]; // take item n int option2 = Integer.MIN_VALUE; if (weight[n] <= w) option2 = profit[n] + opt[n - 1][w - weight[n]]; // select better of two options opt[n][w] = Math.max(option1, option2); sol[n][w] = (option2 > option1); } } // determine which items to take boolean[] take = new boolean[N + 1]; for (int n = N, w = W; n > 0; n--) { if (sol[n][w]) { take[n] = true; w = w - weight[n]; } else { take[n] = false; } } // print results System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take"); for (int n = 1; n <= N; n++) { System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]); } } } 

Answer 5

 import java.util.*; class Main{ static int max(inta,int b) { if(a>b) return a; else return b; } public static void main(String args[]) { int n,i,cap,j,t=2,w; Scanner sc=new Scanner(System.in); System.out.println("Enter the number of values "); n=sc.nextInt(); int solution[]=new int[n]; System.out.println("Enter the capacity of the knapsack :- "); cap=sc.nextInt(); int v[]=new int[n+1]; int wt[]=new int[n+1]; System.out.println("Enter the values "); for(i=1;i<=n;i++) { v[i]=sc.nextInt(); } System.out.println("Enter the weights "); for(i=1;i<=n;i++) { wt[i]=sc.nextInt(); } int knapsack[][]=new int[n+2][cap+1]; for(i=1;i<n+2;i++) { for(j=1;j<n+1;j++) { knapsack[i][j]=0; } } /*for(i=1;i<n+2;i++) { for(j=wt[1]+1;j<cap+2;j++) { knapsack[i][j]=v[1]; } }*/ int k; for(i=1;i<n+1;i++) { for(j=1;j<cap+1;j++) { /*if(i==1||j==1) { knapsack[i][j]=0; }*/ if(wt[i]>j) { knapsack[i][j]=knapsack[i-1][j]; } else { knapsack[i][j]=max(knapsack[i-1][j],v[i]+knapsack[i-1][j-wt[i]]); } } } //for displaying the knapsack for(i=0;i<n+1;i++) { for(j=0;j<cap+1;j++) { System.out.print(knapsack[i][j]+" "); } System.out.print("\n"); } w=cap;k=n-1; j=cap; for(i=n;i>0;i--) { if(knapsack[i][j]!=knapsack[i-1][j]) { j=w-wt[i]; w=j; solution[k]=1; System.out.println("k="+k); k--; } else { solution[k]=0; k--; } } System.out.println("Solution for given knapsack is :- "); for(i=0;i<n;i++) { System.out.print(solution[i]+", "); } System.out.print(" => "+knapsack[n][cap]); } }