Recursive addition

Question

Struggling to write this code.

I'm trying to calculate the highest value from a 2 objects. I started separate "S" and "P" objects:

var S = [
    { id: '1', value: '##' },
    { id: '2', value: '##' },
    { id: '3', value: '##' },
    { id: 'N', value: '##' }
];

var P = [
    { id: '1', value: '##' },
    { id: '2', value: '##' },
    { id: '3', value: '##' },
    { id: 'N', value: '##' }
];

I created an 3rd object:

var myobject = {
    'S1' = {
        'P1' = '25',
        'P2' = '32',
        'P3' = '65',
        'PN' = '##'
    },
    'S2' = {
        'P1' = '24',
        'P2' = '31',
        'P3' = '64',
        'PN' = '##'
    },
    'S3' = {
        'P1' = '26',
        'P2' = '33',
        'P3' = '66',
        'PN' = '##'
    },
    'SN' = {
        'P1' = '##',
        'P2' = '##',
        'P3' = '##',
        'PN' = '##'
    }
};

And I need to iterate through all the values to see with combination produces the highest value, for example:

S1.P1 + S2.P1 + S3.P1 = ?
S1.P1 + S2.P1 + S3.P2 = ?
S1.P1 + S2.P1 + S3.P3 = ?
S1.P1 + S2.P2 + S3.P1 = ?
S1.P1 + S2.P2 + S3.P2 = ?
S1.P1 + S2.P2 + S3.P3 = ?
...

The answer I'm looking for, using the example values above, is:

S1.P3 + S2.P3 + S3.P3 = 195

To complicate things, in some cases, a "P" value may only be used once in the equation:

var P = [
    { id: '1', value: '##' },
    { id: '2', value: '##' },
    { id: '3', value: '##', once: true },
    { id: 'N', value: '##' }
];

If "P3" could only be used once, the answer I'm looking for, using the example values above, is:

S1.P2 + S2.P2 + S3.P3 = 129;

I'm guessing the requires a little recursion....but my head hurts.

EDIT

I'm getting lost in the loops trying to create the calculation, for example:

foreach "S"
    foreach "P"
        foreach "S"
            foreach "P"
                ....

Suggestions?

Surely all you need to do is find the highest value of `Pn` in S1, S2 and S3 and add those together. — Matt Burland, Nov 19 '12 at 18:44
Thanks for the response @MattBurland. Except when the highest value can only be used by one "S", then I need to figure out which "S" uses the "P" — timborden, Nov 19 '12 at 18:47
What is the difference to [Determining the right combination](http://stackoverflow.com/questions/13277834/determining-the-right-combination)? — Bergi, Nov 19 '12 at 18:47
@Bergi: Well they are different functions, though clearly related. — Lightness Races in Orbit, Nov 19 '12 at 18:51
Hey @Bergi...thanks for your interest (again). It's the "use only once" condition for the "P" object that is complicating things (also, I don't really understand how you pulled off the recursion in the last question...if I'm honest) — timborden, Nov 19 '12 at 18:52
@timborden: Well that's simple enough. If a value of `Pn` is use only once and is in your set that gets you the highest value more than once, just keep the highest value of `Pn` and for whichever `Sn` you had to drop, pick the next highest value. Repeat until you satisfy all your conditions. — Matt Burland, Nov 19 '12 at 18:55
@MattBurland: Yes, fixpoint iteration will be the way to go. Yet I think it might be possible that a better result comes up if you drop the higher value from a `Sn` as the values to take instead could interfere with something else and give higher results. — Bergi, Nov 19 '12 at 19:15
@Bergi: Actually, that's a good point. I could get a better result by dropping the highest `Pn`, if the next highest value in `S` is close to `Pn`. You'd have to go through each instance of `Pn` and figure out which one results in the least loss. — Matt Burland, Nov 19 '12 at 19:20
@timborden: Still not seeing an attempt. This is "why do I get X problem" site, not a "tell me how to do the entire Y thing" site. — Lightness Races in Orbit, Nov 19 '12 at 19:28
Hey all...think I solved it (see answer below). Thanks for the comments and suggestions....really helped me out. — timborden, Nov 19 '12 at 19:40
@timborden: You get the lecture for free. Not any more of my time, though. :) — Lightness Races in Orbit, Nov 19 '12 at 19:50

score 6 · Answer 1 · answered Nov 19 '12 at 18:43

6

Since a + b > a + c for any a and all b > c, can't you just get the maximum value from each of S1, S2, S3... and add those together?

I'm not sure I fully understand what you're doing, but this should help avoid too much recursion.

answered Nov 19 '12 at 18:43

Niet the Dark Absol

320,036
81
464
592

Thanks for the response @Kolink. I'm struggling with the "P" value that can only be used once. – timborden Nov 19 '12 at 18:50

score 0 · Accepted Answer · answered Nov 19 '12 at 19:39

Thanks guys....I think I've got something that works.

I changed my object to:

var myobject = {
    'S1-P1' = '25',
    'S1-P2' = '32',
    'S1-P3' = '65',
    'S1-PN' = '##'
    'S2-P1' = '24',
    'S2-P2' = '31',
    'S2-P3' = '64',
    'S2-PN' = '##'
    'S3-P1' = '26',
    'S3-P2' = '33',
    'S3-P3' = '66',
    'S3-PN' = '##'
    'SN-P1' = '##',
    'SN-P2' = '##',
    'SN-P3' = '##',
    'SN-PN' = '##'
};

...and ran it through this:

ids = [];
_.each(S, function(Sn){
    ids.push(Sn.id);
});

var totals = [];
while (ids.length){
    var best = { s_id: null, p_id: null, amount: 0 };
    for (var s1 in myobject) {
        if (best.amount < myobject[s1]){
            id = s1.split('-');
            best = { s_id: id[0], p_id: id[1], amount: myobject[s1] };
        }
    }
    var once = false;
    _.each(P, function(Pn){
        if (Pn.id == best.p_id & Pn.once)
            once = true;
    });
    for (var s2 in myobject) {
        id = s2.split('-');
        if (best.s_id == id[0])
            delete myobject[s2];
        if (once && best.p_id == id[1])
            delete myobject[s2];
    }

    var index = ids.indexOf(best.s_id);
    ids.splice(index, 1);

    totals.push(best);
}
console.log(totals);

....seems to work.

Recursive addition

2 Answers2