Introduction to 0/1 Knapsack Problem

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.

knapsack Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math

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 $tex_c036c4ab6c1fdc6009fa1942d76bae48 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ to put in the knapsack of total weight W. The weights of each items are also known as $tex_efd5f060600114d3337f658f954a1019 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ . 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 $tex_36595b385e10d81cca3e97ba74ace3d7 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ where $tex_a7940f225e252fd87f5740af63e536f2 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ and $tex_76b60d451ad8e7ce0bd598460a6224ea Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$

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 $tex_1cff2c511c9b67f5a0405cf30ea1a847 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$

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 $tex_4753959e4ff08c2b4bebc2eadce5cabf Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ , Otherwise, we decrease the weight by $tex_04acdd2c132520b28284039916bf5dce Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ and add the value of $tex_2cc7f9eb1dd2a7002efbff9d8a766f96 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ .

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 $tex_dc7b9294df11f0390f56d64559a602f1 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ when $tex_ff3fbb2958390ffd7dc4dc1cac114e8d Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$

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 $tex_9084620e8c68b96ee711c16d44639f3d Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ and all others are filled with negative infinity $tex_bdeb49329c9259cd3b26bdec27c05cbe Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ . The first element $tex_67727c9c4b6d2f072dc0562cd76d0517 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ indicates that only item with value zero can fulfil bag of nothing i.e. capacity is zero. In this case, the value $tex_15cf7bc18b56b9fa59f073110032dc16 Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ 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 $tex_0f9b705d28d163b5d25dcfa80c6ea72d Introduction to 0/1 Knapsack Problem algorithms dynamic programming Dynamic Programming Knapsack Problems math$ 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) —

GD Star Rating
loading...

1176 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

Algorithms, Blockchain and Cloud

Introduction to 0/1 Knapsack Problem

Knapsack Problems

Leave a Reply

Knapsack Problems

Related posts:

Leave a Reply