Алгоритм ДП для ограниченного ранца?

Question

Статья Википедии о проблеме ранца содержит списки трех видов:

1. 1-0 (одна единица типа)

2. Ограничено (несколько предметов типа)

3. Неограниченный (неограниченное количество элементов типа)

Статья содержит подходы DP для 1. и 3. типов проблем, но не решение для 2.

Как описать алгоритм динамического программирования для решения 2.

Answer 1

Используйте вариант 0-1, но разрешите повторение элемента в решении до количества раз, указанного в его границе. Вам нужно будет вести вектор, указывающий, сколько копий каждого элемента вы уже включили в частичное решение.

Answer 2

Я разместил статью в 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 включает тестовый пример.

Answer 3

• Сначала сохраните все данные в одном массиве (с повторениями).
• Затем используйте 1-й метод, упомянутый в статье Википедии (1-0).

Например, попытка ограниченного ранца с {2 (2 раза), 4 (3 раза), ...} эквивалентна решению ранца 1-0 с {2, 2, 4, 4, 4, ..)..}.

Answer 4

Я предложу вам использовать Алгоритм Жадного Метода Рюкзака.Это Сложность 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

Answer 5

Мы можем использовать алгоритм ранца 0/1 с отслеживанием количества предметов, оставленных для каждого предмета;

Мы можем сделать то же самое с алгоритмом неограниченного ранца, чтобы решить и проблему ограниченного ранца.