12,945,401 members (82,888 online)
alternative version

#### Stats

25.6K views
16 bookmarked
Posted 8 Jan 2014

# Bounded Knapsack Algorithm

, 8 Jan 2014 CPOL
 Rate this:
The most valuable sack!

## 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:

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.

## Share

 Engineer Comprehend Systems United States
I've been fiddling around with computers since my parents bought me a Commodore VIC-20 for Christmas in 1981.

I received a B.Sc. in Mechanical Engineering from the University of Waterloo, but have spent my career in software development.

I focused on FoxPro during my early career before switching over to .NET and JavaScript.

I created Jooshe and wrote a Code Project article on it.

I wrote the front-end (Jooshe & JavaScript) and middleware (.NET) of dbiScript.

## You may also be interested in...

 First Prev Next
 Question eduinge9-May-16 11:44 eduinge 9-May-16 11:44
 Unbounded knapsack Member 1220196211-Dec-15 15:33 Member 12201962 11-Dec-15 15:33
 Re: Unbounded knapsack eduinge10-Apr-16 4:12 eduinge 10-Apr-16 4:12
 Last Visit: 31-Dec-99 18:00     Last Update: 23-May-17 10:26 Refresh 1