Алгоритм ранца 0-1

Question

Решается ли следующая проблема с ранцем 0-1:

• положительные значения 'float' и
• веса 'float' (могут быть положительными или отрицательными)
• вместимость ранца> 0

у меня в среднем <10 предметов, поэтому я думаю об использовании грубой силы.Однако мне было интересно, есть ли лучший способ сделать это.</p>

Answer 1

Это относительно простая двоичная программа.

Я бы предложил грубую силу с обрезкой. Если в любой момент вы превысите допустимый вес, вам не нужно пробовать комбинации дополнительных предметов, вы можете отказаться от всего дерева.

Ой, подождите, у вас есть отрицательные веса? Всегда включайте все отрицательные веса, затем действуйте как указано выше для положительных весов. Или предметы с отрицательным весом также имеют отрицательное значение?

Включите все элементы с отрицательным весом с положительным значением. Исключить все элементы с положительным весом и отрицательным значением.

Для предметов с отрицательным весом, имеющих отрицательное значение, вычтите их вес (увеличивая емкость рюкзака) и используйте псевдоэлемент, который представляет , а не взятие этого предмета. Псевдоэлемент будет иметь положительный вес и ценность. Продолжить грубой силой с обрезкой.

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-Complete, но это не должно иметь значения, потому что у вас будет менее 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

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

Answer 5

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

}