DP algorithm for bounded Knapsack?

问题:

The Wikipedia article about Knapsack problem contains lists three kinds of it:

1. 1-0 (one item of a type)

2. Bounded (several items of a type)

3. Unbounded (unlimited number of items of a type)

The article contains DP approaches for 1. and 3. types of problem, but no solution for 2.

How can the dynamic programming algorithm for solving 2. be described?

回答1:

Use the 0-1 variant, but allow repetition of an item in the solution up to the number of times specified in its bound. You would need to maintain a vector stating how many copies of each item you already included in the partial solution.

回答2:

I posted an article on Code Project which discusses a more efficient solution to the bounded knapsack algorithm.

From the article:

In the dynamic programming solution, each position of the m array is a sub-problem of capacity j. In the 0/1 algorithm, for each sub-problem we consider the value of adding one copy of each item to the knapsack. In the following algorithm, for each sub-problem we consider the value of adding the lesser of the quantity that will fit, or the quantity available of each item.

I've also enhanced the code so that we can determine what's in the optimized knapsack (as opposed to just the optimized value).

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

}

The download in the Code Project article includes a test case.

回答3:

• First, store all your data in a single array (with repetition).
• Then use the 1st method mentioned in the Wikipedia article(1-0).

For example, trying a bounded knapsack with { 2 (2 times), 4(3 times),...} is equivalent to solving a 1-0 knapsack with {2, 2, 4, 4, 4,...}.

回答4:

I will suggest you to use Knapsack Fraction Greedy Method Algorithm. It's Complexity is O(n log n) and one of the best algorithm. Below I have mentioned its code in 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