DP for a limited backpack?

Question

The Wikipedia article on the knapsack problem contains three views:

1. 1-0 (one type item)

2. Limited (several items of the same type)

3. Unlimited (unlimited number of type elements)

This article contains DP approaches for 1. and 3. types of problems, but not a solution for 2.

How to describe a dynamic programming algorithm for solution 2.?

Answer 1

Use option 0-1, but allow the element to be repeated in the solution up to the number of times specified in its binding. You will need to save the vector by indicating how many copies of each element you have already included in the partial solution.

Answer 2

I posted an article in a draft code that discusses a more efficient solution to the limited backpack algorithm.

From the article:

In a dynamic programming solution, each position of the array m is a sub-problem of capacity j. In the 0/1 algorithm for each sub-task, we consider the value of adding one copy of each element to the backpack. In the following algorithm, for each subtask, we consider the value of adding a smaller amount that will correspond, or the amount available for each element.

I also improved the code so that we can define that in an optimized backpack (as opposed to just an 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 Project Code article includes a test case.

Answer 3

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

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

Answer 4

I suggest you use the Greedy Method Knapsack Fraction algorithm. Difficulty - O (n log n) and one of the best algorithms. Below I 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 

Answer 5

We can use the 0/1 satchel algorithm with tracking the number of items left for each item;

We could do the same on the unlimited knapsack algorithm to solve the limited knapsack problem.