0-1 Knapsack algorithm

问题:

Is the following 0-1 Knapsack problem solvable:

• 'float' positive values and
• 'float' weights (can be positive or negative)
• 'float' capacity of the knapsack > 0

I have on average < 10 items, so I'm thinking of using a brute force implementation. However, I was wondering if there is a better way of doing it.

回答1:

This is a relatively simple binary program.

I'd suggest brute force with pruning. If at any time you exceed the allowable weight, you don't need to try combinations of additional items, you can discard the whole tree.

Oh wait, you have negative weights? Include all negative weights always, then proceed as above for the positive weights. Or do the negative weight items also have negative value?

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

For negative weight items with negative value, subtract their weight (increasing the knapsack capavity) and use a pseudo-item which represents not taking that item. The pseudo-item will have positive weight and value. Proceed by brute force with pruning.

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

回答2:

Yeah, brute force it. This is an NP-Complete problem, but that shouldn't matter because you will have less than 10 items. Brute forcing won't 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();

回答3:

If you can only have positive values then every item with a negative weight must go in.

Then I guess you could calculate Value/Weight Ratio, and brute force the remaining combinations based on that order, once you get one that fits you can skip the rest.

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

There will obviously be a different breakeven point based on the size and distribution of the set.

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

}

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