0-1 Knapsack thuật toán

Question

là sau vấn đề 0-1 Knapsack thể giải quyết được:

• 'phao' giá trị tích cực và
• 'phao' trọng lượng (có thể là tích cực hay tiêu cực)
• 'phao' năng lực của knapsack> 0

Tôi có trung bình < 10 mục, vì vậy tôi đang nghĩ đến việc sử dụng triển khai vũ phu. Tuy nhiên, tôi đã tự hỏi nếu có một cách tốt hơn để làm điều đó.

Answer 1

Đây là chương trình nhị phân tương đối đơn giản.

Tôi muốn đề xuất lực lượng vũ phu bằng cách cắt tỉa. Nếu bất cứ lúc nào bạn vượt quá trọng lượng cho phép, bạn không cần phải thử kết hợp các mục bổ sung, bạn có thể loại bỏ toàn bộ cây.

Ồ, chờ đợi, bạn có âm lượng trọng lượng? Bao gồm tất cả các trọng số âm luôn, sau đó tiến hành như trên cho các trọng số tích cực. Hoặc các mục trọng lượng âm cũng có giá trị âm?

Bao gồm tất cả các mục trọng lượng âm với giá trị dương. Loại trừ tất cả các mục có trọng số dương và giá trị âm.

Đối với các mục trọng lượng âm có giá trị âm, trừ trọng lượng của chúng (tăng độ rộng ba lô) và sử dụng mục giả đại diện cho không lấy mục đó. Các pseudo-item sẽ có trọng lượng và giá trị tích cực. Tiến hành bằng vũ lực bằng cách cắt tỉa.

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

Vâng, sức mạnh vũ phu. Đây là một vấn đề NP-Complete, nhưng điều đó không quan trọng bởi vì bạn sẽ có ít hơn 10 mục. Brute buộc sẽ không có vấn đề.

 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

Nếu bạn chỉ có thể có giá trị tích cực sau đó mỗi mục với một trọng lượng tiêu cực phải đi theo.

Sau đó, tôi đoán bạn có thể tính toán Tỷ lệ giá trị gia tăng/Trọng lượng và sức mạnh tàn bạo các kết hợp còn lại dựa trên thứ tự mà , một khi bạn nhận được một phù hợp với bạn có thể bỏ qua phần còn lại.

Vấn đề có thể là phân loại và phân loại thực sự đắt hơn so với chỉ thực hiện tất cả các tính toán.

Rõ ràng sẽ có một điểm hòa vốn khác nhau dựa trên kích thước và phân phối của tập hợp.

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