有界背包的DP算法？

Question

有界背包的DP算法？

algorithmknapsack-problem

14

"The Wikipedia article about Knapsack problem includes three types of it:

1-0 (one item of each type)
Bounded (several items of the same type)
Unbounded (unlimited number of items of the same type)

The article provides DP approaches for solving problems of type 1 and 3, but doesn't offer a solution for type 2.

How can we describe the dynamic programming algorithm for solving type 2?"

- lithuak

6个回答

7

其他提到的动态规划解决方案都不是最优的，因为它们要求您直接模拟问题，导致运行时间复杂度为 O(物品数量 * 最大重量 * 总物品数)。

有许多方法可以优化这个问题，我将在这里提到其中一些：

一种解决方案是应用类似于Sqrt分解的技术，该技术在此处描述：https://codeforces.com/blog/entry/59606。该算法的时间复杂度为O(物品数量 * 最大重量 * sqrt(最大重量))。

然而，Dorijan Lendvaj在这里描述了一个运行速度更快的算法，其运行时间为O(number of items * maximum weight * log(maximum weight))：https://codeforces.com/blog/entry/65202?#comment-492168 另一种思考上述方法的方式如下：

对于每种物品，定义以下值：

- w，当前物品的重量/成本 - v，当前物品的价值 - n，可用于使用的当前物品副本数

第1阶段

首先，让我们考虑2的k次方，小于或等于n的最大2的幂。我们插入以下项目（每个插入的项目格式为(weight, value)）：(w, v)，(2*w, 2*v)，(2^2*w, 2^2*v)，...，(2^(k-1)*w, 2^(k-1)*v)。请注意，每个插入的项目分别表示当前物品类型的2^0，2^1，...，2^(k-1)个副本。

观察到这与插入2^k - 1个当前类型项目的方式相同。这是因为我们可以通过取与二进制表示n'对应的上述项目的组合来模拟任意数量的项目（对于所有整数k'，如果表示2^k'的位被设置，则取代表2^k'个当前类型项目的项目）。

第二阶段

最后，我们只需插入与n - (2^k - 1)的集合位对应的项目。（对于所有整数k'，如果表示2^k'的位被设置，则插入(2^k' * w, 2^k' * v)）。

现在，我们可以通过取上述插入项目的组合来模拟最多n个当前类型项目的获取。

~~目前我没有确切的证明这个解法的方法，但是在尝试了一段时间之后，它似乎是正确的。如果我找到证明，我可能会稍后更新这篇文章。~~

证明

首先，提出一个命题：我们只需要证明插入上述项目可以让我们模拟取走当前类型的任意数量物品，最多不超过n个。

有了这个想法，让我们定义一些变量：

令n为当前类型可用物品的数量
令x为我们希望取走的当前类型物品的数量
让k是最大的整数，使得2^k <= n

如果x < 2^k，我们可以轻松地使用算法第一阶段描述的方法取走x件物品：

我们可以通过取与n'的二进制表示相对应的上述物品的组合，模拟任意数量的物品（表示为n'），（对于所有的自然数k'，如果表示2^k'的位被设置，则取代表当前物品类型的2^k'个副本的物品）。否则，我们执行以下操作：取n - (2^k - 1)个物品。这是通过获取在第2阶段插入的所有物品完成的。现在，只有在第1阶段插入的物品可供使用。取x - (n - (2^k - 1))个物品。由于该值始终小于2^k，因此我们可以使用用于第一种情况的方法。最后，我们如何知道x - (n - (2^k - 1)) < 2^k？如果简化左边，我们会得到：如果上述值>= 2^k，那么x - (n + 1) >= 0为真，意味着x > n。这是不可能的，因为那不是x的有效值。

最后，这里提到了一种方法在这里，它的运行时间为O(物品数量 * 最大重量)。

该算法类似于ic3b3rg提出的暴力方法，只是使用了简单的DP优化和滑动窗口deque来降低运行时间。

我的代码已经在这个问题上进行了测试（经典有界背包问题）：https://dmoj.ca/problem/knapsack

我的代码：https://pastebin.com/acezMrMY

- Plas

3

我在Code Project上发布了一篇文章，讨论了更有效的有界背包算法解决方案。

从文章中可以看出：

在动态规划解决方案中，m数组的每个位置都是容量为j的子问题。在0/1算法中，对于每个子问题，我们考虑将每个物品的一个副本添加到背包中的价值。在下面的算法中，对于每个子问题，我们考虑添加适合数量或每个物品的可用数量中较小的那个数量的价值。

我还改进了代码，以便我们可以确定优化后的背包中有哪些物品（而不仅仅是优化后的价值）。

ItemCollection[] ic = new ItemCollection[capacity + 1];

for(int i=0;i<=capacity;i++) ic[i] = new ItemCollection();

for(int i=0;i<items.Count;i++)
  for(int j=capacity;j>=0;j--)
    if(j >= items[i].Weight) {
      int quantity = Math.Min(items[i].Quantity, j / items[i].Weight);
      for(int k=1;k<=quantity;k++) {
        ItemCollection lighterCollection = ic[j - k * items[i].Weight];
        int testValue = lighterCollection.TotalValue + k * items[i].Value;
        if(testValue > ic[j].TotalValue) (ic[j] = lighterCollection.Copy()).AddItem(items[i],k);
      }
    }

private class Item {

  public string Description;
  public int Weight;
  public int Value;
  public int Quantity;

  public Item(string description, int weight, int value, int quantity) {
    Description = description;
    Weight = weight;
    Value = value;
    Quantity = quantity;
  }

}

private class ItemCollection {

  public Dictionary<string,int> Contents = new Dictionary<string,int>();
  public int TotalValue;
  public int TotalWeight;

  public void AddItem(Item item,int quantity) {
    if(Contents.ContainsKey(item.Description)) Contents[item.Description] += quantity;
    else Contents[item.Description] = quantity;
    TotalValue += quantity * item.Value;
    TotalWeight += quantity * item.Weight;
  }

  public ItemCollection Copy() {
    var ic = new ItemCollection();
    ic.Contents = new Dictionary<string,int>(this.Contents);
    ic.TotalValue = this.TotalValue;
    ic.TotalWeight = this.TotalWeight;
    return ic;
  }

}

在Code Project文章中的下载包含一个测试用例。

- ic3b3rg

2

首先，将所有数据存储在一个包含重复项的数组中。
然后使用维基百科文章中提到的第一种方法（1-0方法）。

例如，尝试使用{2（2次），4（3次），...}的有界背包等效于使用{2，2，4，4，4，...}解决1-0背包问题。

- Deddy

1

对于一个真实的问题，这种解决方案是不可行的，因为允许重复的次数可能非常大。 - Marlon Patrick

1

我建议您使用背包分数贪心算法。它的复杂度是O(n log n)，是最好的算法之一。下面我在c#中提供了它的代码。

 private static void Knapsack()
        {
            Console.WriteLine("************Kanpsack***************");
            Console.WriteLine("Enter no of items");
            int _noOfItems = Convert.ToInt32(Console.ReadLine());

            int[] itemArray = new int[_noOfItems];
            int[] weightArray = new int[_noOfItems];
            int[] priceArray = new int[_noOfItems];
            int[] fractionArray=new int[_noOfItems];

            for(int i=0;i<_noOfItems;i++)
            {
                Console.WriteLine("[Item"+" "+(i+1)+"]");
                Console.WriteLine("");
                Console.WriteLine("Enter the Weight");
                weightArray[i] = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine("Enter the Price");
                priceArray[i] = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine("");
                itemArray[i] = i+1 ;

            }//for loop

            int temp;
            Console.WriteLine("       ");
            Console.WriteLine("ITEM" + "         " + "WEIGHT" + "         "+"PRICE");
            Console.WriteLine("       ");
            for(int i=0;i<_noOfItems;i++)
            {
                Console.WriteLine("Item"+" "+(i+1)+"       "+weightArray[i]+"               "+priceArray[i]);
                Console.WriteLine(" ");
            }//For Loop For Printing the value.......


            //Caluclating Fraction for the Item............

            for(int i=0;i<_noOfItems;i++)
            {
                fractionArray[i] = (priceArray[i] / weightArray[i]);
            }
            Console.WriteLine("Testing.............");

            //sorting the Item on the basis of fraction value..........

            //Bubble Sort To Sort the Process Priority

            for (int i = 0; i < _noOfItems; i++)
            {
                for (int j = i + 1; j < _noOfItems; j++)
                {
                    if (fractionArray[j] > fractionArray[i])
                    {
                        //item Array
                        temp = itemArray[j];
                        itemArray[j] = itemArray[i];
                        itemArray[i] = temp;

                        //Weight Array
                        temp = weightArray[j];
                        weightArray[j] = weightArray[i];
                        weightArray[i] = temp;

                        //Price Array
                        temp = priceArray[j];
                        priceArray[j] = priceArray[i];
                        priceArray[i] = temp;

                        //Fraction Array
                        temp = fractionArray[j];
                        fractionArray[j] = fractionArray[i];
                        fractionArray[i] = temp;





                    }//if
                }//Inner for
            }//outer For

            // Printing its value..............After Sorting..............
            Console.WriteLine("       ");
            Console.WriteLine("ITEM" + "         " + "WEIGHT" + "         " + "PRICE" + "         "+"Fraction");
            Console.WriteLine("       ");
            for (int i = 0; i < _noOfItems; i++)
            {
                Console.WriteLine("Item" + " " + (itemArray[i]) + "      " + weightArray[i] + "               " + priceArray[i] + "             "+fractionArray[i]);
                Console.WriteLine(" ");
            }//For Loop For Printing the value.......

            Console.WriteLine("");
            Console.WriteLine("Enter the Capacity of Knapsack");
            int _capacityKnapsack = Convert.ToInt32(Console.ReadLine());

            // Creating the valuse for Solution

               int k=0;
               int fractionvalue = 0;
               int[] _takingItemArray=new int[100];

               int sum = 0,_totalPrice=0;
               int l = 0;

               int _capacity = _capacityKnapsack;
              do
              {
                  if(k>=_noOfItems)
                  {
                      k = 0;
                  }

                  if (_capacityKnapsack >= weightArray[k])
                  {
                      _takingItemArray[l] = weightArray[k];
                      _capacityKnapsack = _capacityKnapsack - weightArray[k];
                      _totalPrice += priceArray[k];
                      k++;
                      l++;
                  }
                  else
                  {
                      fractionvalue = fractionArray[k];
                      _takingItemArray[l] = _capacityKnapsack;
                      _totalPrice += _capacityKnapsack * fractionArray[k];
                      k++;
                      l++;

                  }
                  sum += _takingItemArray[l-1];
              } while (sum != _capacity);
              Console.WriteLine("");
              Console.WriteLine("Value in Kg Are............");
              Console.WriteLine("");
              for (int i = 0; i < _takingItemArray.Length; i++)
              {
                  if(_takingItemArray[i]!=0)
                  {
                      Console.WriteLine(_takingItemArray[i]);
                      Console.WriteLine("");
                  }
                  else
                  {
                      break;
                  }
enter code here
              }//for loop
              Console.WriteLine("Toatl Value is "+_totalPrice);

            }//Method

- Prince Sanghi

0

我们可以使用0/1背包算法，对于每个物品跟踪剩余物品的数量；我们也可以在无限背包算法上执行相同的操作，以解决有界背包问题。

- Joe Lee

1

回答问题是好的，但不应该只是重复（部分）现有答案。特别是在旧问题上，新答案应该提供新信息和对主题的深入见解。 - AdrianHHH

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Irit Katriel · Accepted Answer

使用0-1变种，但允许在解决方案中重复一个项目，重复次数取决于其边界指定的次数。您需要维护一个向量，记录已包含在部分解决方案中的每个项目的副本数量。