Knapsack of Integers
Famous programming problem of Packing the Knapsack have several variants. The general statement is like following:
Given a set of items, each of which have some
Value, we want to select some of them to pack into
the knapsack which has limit of
Maximum-Weight. The goal of selection is to maximize the
Total-Value of packet items.
It is told that the problem have a number of appications in transportation, logistics etc - think of building the train of railway cars (with varying content and cost), loading ships with containers or aircrafts with boxes, parcels - besides this it could be the part of more complex algorithms in networking, data transferring software etc.
Three common variants of the problem are:
1) or not (
The last of three is the most popular and so we'll try to solve this. If the weights of the items are given with arbitrary real numbers, the problem can not be solved efficiently. However with integer weights we can use dynamic programming approach, increasing weight by iterations.
Trivial approach would be to try all combinations of items. There are
2^N of them and it will work for about
items in several seconds. However for larger values we are to use dynamic programming.
Suppose we have a set of items, labeled with numbers from
N. Each of them has the known weight
Let us iterate through these items and on each
iteration examine all possible weight limits
Wmax (capacity of knapsack) and try to find the
answer for the given
W and subset of items from
FOR i IN 1..N FOR w IN 0..Wmax subset = items from 1 to i solve_knapsack(subset, w) END FOR END FOR result = solve_knapsack(items from 1 to N, Wmax)
solve_knapsack function returns the value of selected items (for given set and weight limit) and could be
performed in a single choice, using previously calculated values.
i-th element we could either include it or not.
i-1, and the same limit weight
i-1and limit weight
w-w[i](current limit reduced by the weight of item being added) plus the value of the current element
v[i]since it is added.
We only need to choose which value is greater. It will look like:
FUNCTION solve_knapsack(items from 1 to i, weight_limit) valueNo = solve_knapsack(items from 1 to i-1, weight_limit) IF weight_limit < w[i] THEN return valueNo # we can't add current item anyway END IF valueYes = solve_knapsack(items from 1 to i-1, weight_limit - w[i]) + v[i] return max(valueYes, valueNo) END FUNCTION
If we will store previous results given by
solve_knapsack in array (or rectangular matrix since there are two
parameters) we got the DP algorithm. Note that internal "call" to
solve_knapsack can be performed with such a
pair of parameters for which calculation has never taken place before - we should return
0 for such cases.
You are given a set of items - their weights and values. Also you are told the maximum total weight (capacity of the knapsack). Return the maximum possible value of chosen items.
Input data will contain amount of items
N on the first line.
Next line will have the maximum allowed capacity
Wmax of the knapsack.
Then there would be
N lines each with two values -
Answer should have a single value - maximum posible value of items placed into knapsack.
input data: 7 86 5 8 15 20 13 25 15 31 28 65 8 14 23 57 answer: 186
Here items with values
57 are choosen with total weight of