Click here to Skip to main content
12,945,401 members (82,888 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


16 bookmarked
Posted 8 Jan 2014

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


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.


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.


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;




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;


Knapsack Capacity: 1000

Filled Weight: 999

Filled Value: 2535


  • 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.


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


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.

You may also be interested in...

Comments and Discussions

QuestionQuestion Pin
eduinge9-May-16 11:44
membereduinge9-May-16 11:44 
SuggestionUnbounded knapsack Pin
Member 1220196211-Dec-15 15:33
memberMember 1220196211-Dec-15 15:33 
GeneralRe: Unbounded knapsack Pin
eduinge10-Apr-16 4:12
membereduinge10-Apr-16 4:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170518.1 | Last Updated 8 Jan 2014
Article Copyright 2014 by Brien Givens
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid