0-1背包算法

Question

以下 0-1 背包问题是否可解：

• “浮动”正值和
• “浮动”权重（可以是正数或负数）
• 背包的“浮动”容量 > 0

我平均有 < 10 项，所以我正在考虑使用暴力实现。但是，我想知道是否有更好的方法。

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 完全问题，但这并不重要，因为您的项目数少于 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]);
  }
}

Answer 6

这可以使用动态规划来解决。下面的代码可以帮助您使用动态规划解决 0/1 背包问题。

    internal class knapsackProblem
    {
    private int[] weight;
    private int[] profit;
    private int capacity;
    private int itemCount;
    private int[,] data;

    internal void GetMaxProfit()
    {
        ItemDetails();

        data = new int[itemCount, capacity + 1];

        for (int i = 1; i < itemCount; i++)
        {
            for (int j = 1; j < capacity + 1; j++)
            {
                int q = j - weight[i] >= 0 ? data[i - 1, j - weight[i]] + profit[i] : 0;

                if (data[i - 1, j] > q)
                {
                    data[i, j] = data[i - 1, j];
                }
                else
                {
                    data[i, j] = q;
                }
            }
        }

        Console.WriteLine($"\nMax profit can be made : {data[itemCount-1, capacity]}");
        IncludedItems();
    }

    private void ItemDetails()
    {
        Console.Write("\nEnter the count of items to be inserted : ");
        itemCount = Convert.ToInt32(Console.ReadLine()) + 1;
        Console.WriteLine();

        weight = new int[itemCount];
        profit = new int[itemCount];

        for (int i = 1; i < itemCount; i++)
        {
            Console.Write($"Enter weight of item {i} : ");
            weight[i] = Convert.ToInt32(Console.ReadLine());

            Console.Write($"Enter the profit on the item {i} : ");
            profit[i] = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine();
        }

        Console.Write("\nEnter the capacity of the knapsack : ");
        capacity = Convert.ToInt32(Console.ReadLine());
    }

    private void IncludedItems()
    {
        int i = itemCount - 1;
        int j = capacity;

        while(i > 0)
        {
            if(data[i, j] == data[i - 1, j])
            {
                Console.WriteLine($"Item {i} : Not included");
                i--;
            }
            else
            {
                Console.WriteLine($"Item {i} : Included");
                j = j - weight[i];
                i--;
            }
        }
    }
}