Thursday, March 17, 2011

Problem with Values and Weights

You are given two numbers V and W
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·v V
and
                                         wk  + 2·wj + 3·w 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·v V
                                         w1  + 2·w3 + 3·w W



as:

                              5  + 2·(3) + 3·(1)  14
and
                                            5  + 2·(4) + 3·(1)  16

No comments:

Post a Comment