Click here to Skip to main content
Click here to Skip to main content

Tagged as

Bounded Knapsack Algorithm

, 8 Jan 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Brien Givens
Engineer Comprehend Systems
United States 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.
 
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web03 | 2.8.141022.1 | Last Updated 8 Jan 2014
Article Copyright 2014 by Brien Givens
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid