0-1ナップザックアルゴリズム

Question

が解ける以下0-1ナップザック問題である：

• 「フロート」の正の値と
• 「フロート」の重み（正または負であり得る）
• 「フロート」ナップザックの容量> 0

私は平均して<のアイテムを持っていますので、ブルートフォースの実装を考えています。しかし、もっと良い方法があるのだろうかと思っていました。

Answer 1

これは比較的単純なバイナリプログラムです。

私は、枝刈りで無理矢理力を発揮します。許容重量を超過すると、追加アイテムの組み合わせを試す必要はなく、ツリー全体を破棄することができます。

ああ待って、あなたは負のの重みを持っていますか？すべての負の重みを常に含めてから、正の重みに対して上記のように処理します。または負の重みのアイテムも負の値を持っていますか？

正の値を持つ負のウェイトアイテムをすべて含めます。正の重みと負の値を持つすべてのアイテムを除外します。負の値と負の重みの項目について

、（ナップザックcapavity増加）その重量を減算し、そのアイテムを取るないを表す疑似アイテムを使用します。疑似アイテムは正の重みと値を持ちます。枝打ちして無理矢理遂行しなさい。

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

ええ、ブルートフォース。これはNP完全な問題ですが、10項目未満で済むので問題はありません。ブルートフォースは問題ありません。

 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

あなたは正の値のみを持つことができる場合は、負の重みを持つすべての項目は。

に行かなければならないそれから私はあなたがその順序に基づいて、残りの組み合わせをバリュー/重量比を計算し、力ずくことができると思います、あなたが合うものを手に入れたら、残りのものを飛ばすことができます。

問題は、グレーディングと並べ替えがすべての計算を行うよりも実際にはコストがかかることがあります。

明らかに、セットのサイズと分布に基づいて異なる損害ポイントが存在します。

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