V represents a total value
W represents a total weight.
You are also given 9 items (each one of them has a value and a weight). These are given as nine value,weight pairs. The format is as shown below:
V W
v1 w1
v2 w2
v3 w3
v4 w4
v5 w5
v6 w6
v7 w7
v8 w8
v9 w9
Your task is the following:
Are there three items i,j,k with respective values vi,vj,vk and respective weights wi,wj,wk such that:
vi + 2·vj + 3·vk ≤ V
and
wk + 2·wj + 3·wi ≤ W
Print any one of such such triplet if there are any, in the right order i,j,k
else print NO.
Example
input:
14 16
1 5
2 8
3 4
8 3
5 1
5 6
3 10
9 5
1 10
output: 5,3,1
Precisely:
v5 + 2·v3 + 3·v1 ≤ V
w1 + 2·w3 + 3·w5 ≤ W
as:
5 + 2·(3) + 3·(1) ≤ 14
and
5 + 2·(4) + 3·(1) ≤ 16
No comments:
Post a Comment