Knapsack problem/Continuous: Difference between revisions

=={{header|jq}}==

{{ works with|jq|1.4}}

<lang jq># continuous_knapsack(W) expects the input to be

# an array of objects {"name": _, "weight": _, "value": _}

# where "value" is the value of the given weight of the object.

def continuous_knapsack(W):

map( .price = (if .weight > 0 then (.value/.weight) else 0 end) )

| sort_by( .price )

| reverse

| reduce .[] as $item

# state: [array, capacity]

([[], W];

.[1] as $c

| if $c <= 0 then .

else ( [$item.weight, $c] | min) as $min

| [.[0] + [ $item | (.weight = $min) | .value = (.price * $min)],

($c - $min) ]

end)

| .[1] as $remainder

| .[0]

| (.[] | {name, weight}),

"Total value: \( map(.value) | add)",

"Total weight: \(W - $remainder)" ;</lang>

'''The task:'''

<lang jq>def items: [

{ "name": "beef", "weight": 3.8, "value": 36},

{ "name": "pork", "weight": 5.4, "value": 43},

{ "name": "ham", "weight": 3.6, "value": 90},

{ "name": "greaves", "weight": 2.4, "value": 45},

{ "name": "flitch", "weight": 4.0, "value": 30},

{ "name": "brawn", "weight": 2.5, "value": 56},

{ "name": "welt", "weight": 3.7, "value": 67},

{ "name": "salami", "weight": 3.0, "value": 95},

{ "name": "sausage", "weight": 5.9, "value": 98} ];

items | continuous_knapsack(15)</lang>

{{out}}

<lang sh>$ jq -r -c -n -f knapsack_continuous.jq

{"name":"salami","weight":3}

{"name":"ham","weight":3.6}

{"name":"brawn","weight":2.5}

{"name":"greaves","weight":2.4}

{"name":"welt","weight":3.5000000000000004}

Total value: 349.3783783783784

Total weight: 15</lang>