44 lines
1.2 KiB
Awk
44 lines
1.2 KiB
Awk
# syntax: GAWK -f KNAPSACK_PROBLEM_0-1.AWK
|
|
BEGIN {
|
|
# arr["item,weight"] = value
|
|
arr["map,9"] = 150
|
|
arr["compass,13"] = 35
|
|
arr["water,153"] = 200
|
|
arr["sandwich,50"] = 160
|
|
arr["glucose,15"] = 60
|
|
arr["tin,68"] = 45
|
|
arr["banana,27"] = 60
|
|
arr["apple,39"] = 40
|
|
arr["cheese,23"] = 30
|
|
arr["beer,52"] = 10
|
|
arr["suntan cream,11"] = 70
|
|
arr["camera,32"] = 30
|
|
arr["T-shirt,24"] = 15
|
|
arr["trousers,48"] = 10
|
|
arr["umbrella,73"] = 40
|
|
arr["waterproof trousers,42"] = 70
|
|
arr["waterproof overclothes,43"] = 75
|
|
arr["note-case,22"] = 80
|
|
arr["sunglasses,7"] = 20
|
|
arr["towel,18"] = 12
|
|
arr["socks,4"] = 50
|
|
arr["book,30"] = 10
|
|
sack_size = 400 # dag
|
|
PROCINFO["sorted_in"] = "@val_num_desc"
|
|
for (i in arr) {
|
|
if (total_weight >= sack_size) {
|
|
break
|
|
}
|
|
split(i,tmp,",")
|
|
weight = tmp[2]
|
|
if (total_weight + weight <= sack_size) {
|
|
printf("%s\n",tmp[1])
|
|
total_items++
|
|
total_value += arr[i]
|
|
total_weight += weight
|
|
}
|
|
}
|
|
printf("items=%d (out of %d) weight=%d value=%d\n",total_items,length(arr),total_weight,total_value)
|
|
exit(0)
|
|
}
|