0-1 algoritmo Knapsack

Question

è il seguente problema 0-1 Knapsack risolvibile:

• 'float' valori positivi e
• pesi 'float' (può essere positivo o negativo)
• 'float' capacità dello zaino> 0

Ho in media < 10 elementi, quindi sto pensando di utilizzare un'implementazione forza bruta. Tuttavia, mi chiedevo se c'è un modo migliore per farlo.

Answer 1

Questo è un programma binario relativamente semplice.

Suggerisco forza bruta con la potatura. Se in qualsiasi momento si supera il peso consentito, non è necessario provare combinazioni di elementi aggiuntivi, è possibile scartare l'intero albero.

Oh aspetta, hai negativo pesi? Includere sempre tutti i pesi negativi, quindi procedere come sopra per i pesi positivi. Oppure gli articoli con peso negativo hanno anche un valore negativo?

Includere tutte le voci di peso negativo con valore positivo. Escludere tutti gli articoli con peso positivo e valore negativo.

Per le voci di peso negativo con valore negativo, sottrarre il loro peso (aumentando la capavità dello zaino) e utilizzare uno pseudo-articolo che rappresenta non prendendo quell'elemento. Lo pseudo articolo avrà un peso e un valore positivi. Procedi con la forza bruta con la potatura.

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

Sì, forza bruta. Questo è un problema NP-Completo, ma ciò non dovrebbe avere importanza perché avrai meno di 10 elementi. Forza brutale non sarà problematico.

 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

Se si può avere solo valori positivi allora ogni elemento con un peso negativo deve andare in.

Poi Credo che si potrebbe calcolare il rapporto valore/peso, e la forza bruta le combinazioni rimanenti in base a tale ordine , una volta ottenuto quello che si adatta, puoi saltare il resto.

Il problema può essere che il livellamento e l'ordinamento sono in realtà più costosi del semplice fare tutti i calcoli.

Ci sarà ovviamente un diverso punto di pareggio in base alla dimensione e alla distribuzione del 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]); 
    } 
}