Bounded Knapsack Algorithm

• Download source - 1.2 KB

Using the Code

The attached file is an HttpHandler written in C#.

Introduction

A common solution to the bounded knapsack problem is to refactor the inputs to the 0/1 knapsack algorithm. This article presents a more efficient way of handling the bounded knapsack problem.

Background

The knapsack problem aims to maximize the combined value of items placed into a knapsack of limited capacity. The knapsack problem has a long history, dating back to at least 1897 and possibly much earlier.

For a single knapsack, there are three basic versions of the problem:

• Unbounded
• 0/1
• Bounded

The unbounded knapsack problem is fairly easy to solve:

1. Determine the value-weight ratio of every item.
2. Starting with the highest value-weight ratio item, place as many of this item as will fit into the sack.
3. Move onto the next-highest value-weight item and repeat step 2 until the sack is full or there are no other items.

The 0/1 version of the problem introduces a bound of 1 for every item; you either place the item in the knapsack, or you don't. The dynamic programming pseudocode listed on Wikipedia is an efficient way to solve the problem. Here's the 1-dimensional array version for C#:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

int[] m = new int[W + 1];

for(int i=0;i<n;i++)
  for(int j=W;j>=0;j--)
    m[j] = j < w[i] ? m[j] : Math.Max(m[j], m[j - w[i]] + v[i]);

The optimized value for capacity W is stored in m[W].

Wikipedia states that the 0/1 version is the most common problem being solved. It seems to me that a bounded version with varying quantities of each item is a more realistic scenario. A little searching seems to indicate that the common way of handling a bounded knapsack problem is to refactor the inputs to the 0/1 algorithm. I present a more efficient way to handle the problem.

Explanation

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

Item Class

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

}

ItemCollection Class

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

}

Test

Input

var items = new List<Item>(){
  new Item("Apple", 39, 40, 4),
  new Item("Banana", 27, 60, 4),
  new Item("Beer", 52, 10, 12),
  new Item("Book", 30, 10, 2),
  new Item("Camera", 32, 30, 1),
  new Item("Cheese", 23, 30, 4),
  new Item("Chocolate Bar", 15, 60, 10),
  new Item("Compass", 13, 35, 1),
  new Item("Jeans", 48, 10, 1),
  new Item("Map", 9, 150, 1),
  new Item("Notebook", 22, 80, 1),
  new Item("Sandwich", 50, 160, 4),
  new Item("Ski Jacket", 43, 75, 1),
  new Item("Ski Pants", 42, 70, 1),
  new Item("Socks", 4, 50, 2),
  new Item("Sunglasses", 7, 20, 1),
  new Item("Suntan Lotion", 11, 70, 1),
  new Item("T-Shirt", 24, 15, 1),
  new Item("Tin", 68, 45, 1),
  new Item("Towel", 18, 12, 1),
  new Item("Umbrella", 73, 40, 1),
  new Item("Water", 153, 200, 1)
};

int capacity = 1000;

Output

Knapsack Capacity: 1000

Filled Weight: 999

Filled Value: 2535

Contents:

• Apple (3)
• Banana (4)
• Cheese (4)
• Chocolate Bar (10)
• Compass (1)
• Map (1)
• Notebook (1)
• Sandwich (4)
• Ski Jacket (1)
• Ski Pants (1)
• Socks (2)
• Sunglasses (1)
• Suntan Lotion (1)
• T-Shirt (1)
• Water (1)

Note: The number in brackets indicates the quantity of each item placed in the knapsack.