Introduction to 0/1 Knapsack Problem

ACMer

14 years ago

In reality, many applications can be represented as Knapsack problems. The knapsack problem is one of the most classic combinatics mathematics problems. The knapscak problems are of serveral types. It can be further classified into 0/1 Knapsack problem, multi-dimensional knapsack problem, fraction knapsack etc depending upon the rules to put valuables in knapsacks.

The 0/1 Knapsack problem is the most basic form and it can be easily solved using Dynamic Programming, currently known the best solution to this type of problem.

The problem can be described as: Given n items with values to put in the knapsack of total weight W. The weights of each items are also known as . The problem is to maximize the total values of the items that can be put in the knapsack.

Mathematically this can be represented by the following optimization problem:

Maximize where and

The values and weights are all assumed non-negative.

Using Dynamic Programming, the above problem can be solved using the following recursive expressions.

Assume f(i, w) represents the maximum values of choosing the first i items that do not exceed the total weight w.

The recursive formula is

At the point of item i, we have two options, either choosing it or not choosing it. The answer is the maximum of the two decisions. By not choosing it, we have the answer of , Otherwise, we decrease the weight by and add the value of .

By this method, the problem is divided into the problems of smaller sizes. We can easily implement this by recursive functions.

It is obvious that we can not choose item i, if the current item exceeds the weight limit, the answer is when

If the requirement to pack the knapsack is to perfectly fill the knapsack, i.e. the total weights of all items put into the knapsack is equal to the maximum capacity, we should initialize and all others are filled with negative infinity . The first element indicates that only item with value zero can fulfil bag of nothing i.e. capacity is zero. In this case, the value is the answer of the maximum value obtained by filling all knapsack.

The other possible case is that not all the knapsacks’ capacity is used, i.e. there is room possibly. In this case, we initialize all elements of with zero meaning that we have answers for every single knapsack’s capacity, using nothing to fill and the value is zero.

Knapsack Problems

–EOF (The Ultimate Computing & Technology Blog) —

1159 words
Last Post: Codeforces: B. Spreadsheets
Next Post: Optimal SizeOf Code Generated in Delphi 2007

The Permanent URL is: Introduction to 0/1 Knapsack Problem (AMP Version)

Knapsack Problems

Related posts: