Knapsack problem/Unbounded
You are encouraged to solve this task according to the task description, using any language you may know.
A traveller gets diverted and has to make an unscheduled stop in what turns out to be Shangri La. Opting to leave, he is allowed to take as much as he likes of the following items, so long as it will fit in his knapsack, and he can carry it. He knows that he can carry no more than 25 'weights' in total; and that the capacity of his knapsack is 0.25 'cubic lengths'.
Looking just above the bar codes on the items he finds their weights and volumes. He digs out his recent copy of a financial paper and gets the value of each item.
| Item | Explanation | Value (each) | weight | Volume (each) |
| panacea (vials of) | Incredible healing properties | 3000 | 0.3 | 0.025 |
| ichor (ampules of) | Vampires blood | 1800 | 0.2 | 0.015 |
| gold (bars) | Shiney shiney | 2500 | 2.0 | 0.002 |
| Knapsack | For the carrying of | - | <=25 | <=0.25 |
He can only take whole units of any item,, but there is much more of any item than he could ever carry
How many of each item does he take to maximise the value of items he is carrying away with him?
Note:
- There are four solutions that maximise the value taken. Only one need be given.
C
<c>#include <stdio.h>
- define MIN(a,b) ( ((a)<(b)) ? (a) : (b) )
struct Bounty {
int value; double weight; double volume;
};
double totalWeight, totalVolume; int maxPanacea, maxIchor, maxGold, maxValue = 0; int n[3];
struct Bounty panacea = {3000, 0.3, 0.025},
ichor = {1800, 0.2, 0.015},
gold = {2500, 2.0, 0.002},
sack = { 0, 25.0, 0.25 },
current;
- define CALC(V) current.V = i*panacea.V + j*ichor.V + k*gold.V
int main() {
int i, j, k;
maxPanacea = MIN( sack.weight / panacea.weight, sack.volume / panacea.volume );
maxIchor = MIN( sack.weight / ichor.weight, sack.volume / ichor.volume );
maxGold = MIN( sack.weight / gold.weight, sack.volume / gold.volume );
for(i=0; i < maxPanacea ; i++ )
{
for(j=0; j < maxIchor ; j++ )
{
for(k=0; k < maxGold ; k++ )
{
CALC(value);
CALC(weight);
CALC(volume);
if ( ( current.weight > sack.weight ) ||
( current.volume > sack.volume ) ) continue;
if ( current.value > maxValue )
{
maxValue = current.value;
totalWeight = current.weight;
totalVolume = current.volume;
n[0] = i; n[1] = j; n[2] = k;
}
}
}
}
printf("Maximum value achievable is %d\n"
"This is achieved by carrying %d panacea, %d ichor and %d gold\n"
"The weight to carry is %4.1f and the volume used is %5.3f\n",
maxValue,
n[0], n[1], n[2],
totalWeight, totalVolume);
}</c>
Forth
\ : value ; immediate
: weight cell+ ;
: volume 2 cells + ;
: number 3 cells + ;
\ item value weight volume number
create panacea 30 , 3 , 25 , 0 ,
create ichor 18 , 2 , 15 , 0 ,
create gold 25 , 20 , 2 , 0 ,
create sack 0 , 250 , 250 ,
: fits? ( item -- ? )
dup weight @ sack weight @ > if drop false exit then
volume @ sack volume @ > 0= ;
: add ( item -- )
dup @ sack +!
dup weight @ negate sack weight +!
dup volume @ negate sack volume +!
1 swap number +! ;
: take ( item -- )
dup @ negate sack +!
dup weight @ sack weight +!
dup volume @ sack volume +!
-1 swap number +! ;
variable max-value
variable max-pan
variable max-ich
variable max-au
: .solution
cr
max-pan @ . ." Panaceas, "
max-ich @ . ." Ichors, and "
max-au @ . ." Gold for a total value of "
max-value @ 100 * . ;
: check
sack @ max-value @ <= if exit then
sack @ max-value !
panacea number @ max-pan !
ichor number @ max-ich !
gold number @ max-au !
( .solution ) ; \ and change <= to < to see all solutions
: solve-gold
check
gold fits? if gold add recurse gold take then ;
: solve-ichor
check
ichor fits? if ichor add recurse ichor take then
solve-gold ;
: solve-panacea
check
panacea fits? if panacea add recurse panacea take then
solve-ichor ;
\ init max-value to a possible solution (10 panaceas) for speed
panacea @ 10 * max-value !
solve-panacea .solution
Fortran
A straight forward 'brute force' approach
PROGRAM KNAPSACK
IMPLICIT NONE
REAL :: totalWeight, totalVolume
INTEGER :: maxPanacea, maxIchor, maxGold, maxValue = 0
INTEGER :: i, j, k
INTEGER :: n(3)
TYPE Bounty
INTEGER :: value
REAL :: weight
REAL :: volume
END TYPE Bounty
TYPE(Bounty) :: panacea, ichor, gold, sack, current
panacea = Bounty(3000, 0.3, 0.025)
ichor = Bounty(1800, 0.2, 0.015)
gold = Bounty(2500, 2.0, 0.002)
sack = Bounty(0, 25.0, 0.25)
maxPanacea = MIN(sack%weight / panacea%weight, sack%volume / panacea%volume)
maxIchor = MIN(sack%weight / ichor%weight, sack%volume / ichor%volume)
maxGold = MIN(sack%weight / gold%weight, sack%volume / gold%volume)
DO i = 0, maxPanacea
DO j = 0, maxIchor
Do k = 0, maxGold
current%value = k * gold%value + j * ichor%value + i * panacea%value
current%weight = k * gold%weight + j * ichor%weight + i * panacea%weight
current%volume = k * gold%volume + j * ichor%volume + i * panacea%volume
IF (current%weight > sack%weight .OR. current%volume > sack%volume) CYCLE
IF (current%value > maxValue) THEN
maxValue = current%value
totalWeight = current%weight
totalVolume = current%volume
n(1) = i ; n(2) = j ; n(3) = k
END IF
END DO
END DO
END DO
WRITE(*, "(A,I0)") "Maximum value achievable is ", maxValue
WRITE(*, "(3(A,I0),A)") "This is achieved by carrying ", n(1), " panacea, ", n(2), " ichor and ", n(3), " gold items"
WRITE(*, "(A,F4.1,A,F5.3)") "The weight to carry is ", totalWeight, " and the volume used is ", totalVolume
END PROGRAM KNAPSACK
Sample output
Maximum value achievable is 54500 This is achieved by carrying 0 panacea, 15 ichor and 11 gold items The weight to carry is 25.0 and the volume used is 0.247
Python
<python>from itertools import product from collections import namedtuple from pprint import pprint as pp
Bounty = namedtuple('Bounty', 'name value weight volume') items = [ Bounty('panacea', 3000, 0.3, 0.025),
Bounty('ichor', 1800, 0.2, 0.015),
Bounty('gold', 2500, 2.0, 0.002),
]
sack = Bounty('sack', 0, 25.0, 0.25)
def totvalue(itemscount, items=items, sack=sack):
"""\
Given the count of each item in the sack return -1 if they can't be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
weight = sum( n*item.weight for n, item in zip(itemscount, items) )
volume = sum( n*item.volume for n, item in zip(itemscount, items) )
if weight > sack.weight or volume > sack.volume:
return -1, 0, 0
return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume
def knapsack(items = items, sack = sack):
# find max of any one item
max1 = [ min(int(sack.weight/item.weight), int(sack.volume/item.volume))
for item in items ]
# Try all combinations of bounty items from 0 up to max1 return max( product(*[range(n+1) for n in max1]), key = totvalue )
maxitems = knapsack() maxvalue, maxweight, maxvolume = totvalue(maxitems) maxweight = -maxweight; maxvolume = -maxvolume
print "The maximum value achievable (by exhaustive search) is %g" % maxvalue print " The number of %s items to achieve this is: %s, respectively" % (
','.join(item.name for item in items), maxitems )
print " The weight to carry is %.3g, and the volume used is %.3g" % (
maxweight, maxvolume )
- debug print of sorted values
- max1 = [ min(int(sack.weight/item.weight), int(sack.volume/item.volume))
- for item in items ]
- pp( sorted( (totvalue(num), num) for num in product(*[range(n+1) for n in max1]) )[-20:] )
</python>
Sample output
The maximum value achievable (by exhaustive search) is 54500 The number of panacea,ichor,gold items to achieve this is: (9, 0, 11), respectively The weight to carry is 24.7, and the volume used is 0.247
Dynamic Programming solution
A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(wv) space and O(wvn) time, where w = weight of sack, v = volume of sack, n = number of types of items.
<python># Bounty = namedtuple('Bounty', 'name value weight volume')
- The above didn't work for me. I used this instead:
class Bounty:
def __init__(self, name, value, weight, volume):
self.name = name
self.value = value
self.weight = weight
self.volume = volume
items = [ Bounty('panacea', 3000, 3, 25),
Bounty('ichor', 1800, 2, 15),
Bounty('gold', 2500, 20, 2),
]
sack = Bounty('sack', 0, 250, 250)
def totvalue(itemscount, items=items, sack=sack):
"""\
Given the count of each item in the sack return -1 if they can't be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
weight = sum( n*item.weight for n, item in zip(itemscount, items) )
volume = sum( n*item.volume for n, item in zip(itemscount, items) )
if weight > sack.weight or volume > sack.volume:
return -1, 0, 0
return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume
def knapsack_dp(items = items, sack = sack):
""" Solves the Knapsack problem, with two sets of weights, using a dynamic programming approach """
# (weight+1) x (volume+1) table
# table[w][v] is the maximum value that can be achieved
# with a sack of weight w and volume v.
# They all start out as 0 (empty sack)
table = [ [0] * (sack.volume+1) for i in range(sack.weight+1) ]
for w in range(0, sack.weight+1):
for v in range(0, sack.volume+1):
# Consider the optimal solution, and consider the "last item" added
# to the sack. Removing this item must produce an optimal solution
# to the subproblem with the sack's weight and volume reduced by that
# of the item. So we search through all possible "last items":
for item in items:
# Only consider items that would fit:
if w >= item.weight and v >= item.volume:
table[w][v] = \
max(table[w][v],
# Optimal solution to subproblem + value of item:
table[w-item.weight][v-item.volume] + item.value)
# Backtrack through matrix to re-construct optimum:
result = [0] * len(items)
w = sack.weight; v = sack.volume
while table[w][v] != 0:
# Find the last item that was added:
i = [table[w-item.weight][v-item.volume] + item.value
for item in items].index(table[w][v])
# Record it in the result, and remove it:
result[i] += 1
w -= items[i].weight
v -= items[i].volume
return result
maxitems = knapsack_dp() maxvalue, maxweight, maxvolume = totvalue(maxitems) maxweight = -maxweight; maxvolume = -maxvolume
print "The maximum value achievable (by dynamic programming) is %g" % maxvalue print " The number of %s items to achieve this is: %s, respectively" % (
','.join(item.name for item in items), maxitems )
print " The weight to carry is %d, and the volume used is %d" % (
maxweight, maxvolume )</python>
Sample output
The maximum value achievable (by dynamic programming) is 54500 The number of panacea,ichor,gold items to achieve this is: [9, 0, 11], respectively The weight to carry is 247, and the volume used is 247