0-1背包算法

7
以下是可行的0-1背包问题解决方案:
  • 使用‘浮点数’表示正值和
  • 使用‘浮点数’表示重量(可以为正数或负数)
  • 使用‘浮点数’表示背包容量 > 0
考虑到平均不到10个物品,因此可以使用暴力实现。但是,我们是否有更好的方法呢?

4
你是真的想表达“可解决”,还是“能够高效地解决”? - BlueRaja - Danny Pflughoeft
如果您不需要精确的答案,可以考虑模拟退火算法。 - Mike Christensen
3
2的10次方等于1024。无论是否存在“更好”的方法,都应该采用暴力方法,即使这种方法几乎肯定会更慢。 - Doug McClean
那么,“正值”和“权重”之间有什么区别?你想要达到什么目标? - McKay
2
@McKay:每个物品都有一个价值和重量。我们希望最大化价值的总和,使得重量的总和<=背包容量。 - j_random_hacker
6个回答

9

这是一个相对简单的二进制程序。

我建议使用剪枝的暴力破解法。如果你超过了允许的重量,就不需要尝试其他物品的组合,可以放弃整个树。

哦,等等,你有负重吗?总是包括所有负重,然后按上述方法处理正重量。或者负重物品也有负价值吗?

包括所有带有正价值的负重物品。排除所有带有正重量和负价值的物品。

对于负重物品带有负价值的情况,减去它们的重量(增加背包容量),并使用一个代表不取该物品的伪物品。该伪物品将具有正重量和价值。采用剪枝的暴力破解法进行处理。

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

1
我认为修剪可能不是一个好主意?它增加了开销(在检查方面),并且并没有节省太多时间,但这取决于溢出的可能性有多大,特别是如果您还必须根据正负重量将物品放入垃圾箱中。 - McKay
2
@j_random_hacker:再检查一下,这里没有减法。之前的值是从调用堆栈中恢复的(调用者有一个未修改的副本)。 - Ben Voigt
1
@alhazen,那只是第二种“权重”。添加一个currentCount参数和一个countLimit字段。 - Ben Voigt
这段代码在与我的数据集相同的情况下运行时间只有1毫秒(10k批处理需要100毫秒),但我仍然需要更改我的代码以实际解决背包问题(而不是目标求和),所以这并不是一个公平的比较,但是这种方法更快。 - McKay
1
@BenVoigt 我更新了我的代码,现在它实际上正在解决背包问题的这个版本。而且我得到的价值比你更高,也就是说,当我们在同一个集合上运行时,我将更高价值的物品放入我的袋子中。也许我做错了什么?也许你做错了什么?愿意查看我的代码吗?它应该相当简单。你的代码需要进一步分解,以确保覆盖所有路径。 - McKay
显示剩余7条评论

4

好的,采用暴力破解方式。虽然这是一个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();

1
谢谢你的回复。但是我认为你的代码返回的是满足约束条件的第一个有效组合,而不是总价值尽可能大且满足约束条件的组合。 - alhazen
1
你能否帮我性能测试一下我的递归解决方案,因为你已经有了测试框架? - Ben Voigt
@McKay:现在已经修复了,我想。至少它可以编译,除了缺少“Main”之外。 - Ben Voigt
2
很抱歉,这段代码并没有解决背包问题: -1。并且使用位运算比生成二进制数字字符串更简单、更快速。在C语言中,您可以用if ((i >> j) & 1) 替换 if (splitOut[j] == '1') ,我相信在C#中语法也类似。 - j_random_hacker
1
谢谢您的更新,麦凯。这是一个简单而美妙的实现,可以良好地处理正负权重。干杯! - alhazen
显示剩余4条评论

1

如果您只能使用正值,则每个具有负重量的项目都必须进入。

然后,我想你可以计算价值/重量比,并基于该顺序强制执行其余组合,一旦找到适合您的组合,就可以跳过其余部分。

问题可能是评分和排序实际上比进行所有计算更昂贵。

显然,基于集合的大小和分布,将会有不同的盈亏平衡点。


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

}

时间复杂度为O(NW),空间复杂度也为O(NW)。 - Arvind Telharkar

0

这个问题可以通过动态规划来解决。下面的代码可以帮助您使用动态规划解决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--;
            }
        }
    }
}

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接