in reply to maximizing value from a set of objects

Your question leaves lots of things unspecified. For example:

  1. How many items are to be considered?

    For a low number of items, a simple exhaustive search runs quickly enough:

    #! perl -slw use strict; use Data::Dump qw[ pp ]; use Algorithm::Combinatorics qw[ variations variations_with_repetition + ]; use List::Util qw[ sum ]; my %objects = map{ shift @$_ => $_ } map[ split ], <DATA>; pp \%objects; my $iter = variations( [ keys %objects ], 3 ); my( $bestValue, @bestSet ) = 0; while( my $set = $iter->next ) { my $cost = sum( map{ $objects{ $_ }[0] } @$set ); if( $cost <= 25 ) { my $value = sum( map{ $objects{ $_ }[ 1 ] } @$set ); if( $value >= $bestValue ) { $bestValue = $value; @bestSet = @$set; print "[@$set] => cost:$cost value:$value"; } } } print "Best: @bestSet => $bestValue"; #object cost($) value __DATA__ A 6 16 B 7 14 C 8 19 D 8 17 E 10 20

    Outputs:

    C:\test>1147022.pl { A => [6, 16], B => [7, 14], C => [8, 19], D => [8, 17], E => [10, 20 +] } [A D C] => cost:22 value:52 [A D E] => cost:24 value:53 [A C E] => cost:24 value:55 [A E C] => cost:24 value:55 [C A E] => cost:24 value:55 [C E A] => cost:24 value:55 [E A C] => cost:24 value:55 [E C A] => cost:24 value:55 Best: E C A => 55

    But for large numbers of items, this exhaustive search could take a very long time.

  2. How do you determine "best value"?

    Looking at the results above there are several ways of getting $55 worth of goods for $24 outlay; but they result in a 'profit' of 229%.

    However, for $22 outlay, you can get $52 worth of value resulting in a 236% 'markup'.

  3. You don't state whether you can purchase multiples of a given item?

    If you can, then switching from variations() to variations_with_repetition() gives a different set of results:

    C:\test>1147022.pl { A => [6, 16], B => [7, 14], C => [8, 19], D => [8, 17], E => [10, 20 +] } [A A A] => cost:18 value:48 [A A D] => cost:20 value:49 [A A C] => cost:20 value:51 [A A E] => cost:22 value:52 [A D C] => cost:22 value:52 [A D E] => cost:24 value:53 [A C C] => cost:22 value:54 [A C E] => cost:24 value:55 [A E C] => cost:24 value:55 [D C C] => cost:24 value:55 [C A E] => cost:24 value:55 [C D C] => cost:24 value:55 [C C D] => cost:24 value:55 [C C C] => cost:24 value:57 Best: C C C => 57

    And a different 'winner'.

You need to clarify your problem description.

Also, on the basis of previous experience of answering questions here; "simplifying" the problem description nearly always results in wasting a lot of people's time because they solve the problem you've described in a way that isn't applicable to the real problem. It's nearly always a false policy.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: maximizing value from a set of objects
by GotToBTru (Prior) on Nov 05, 2015 at 20:22 UTC

    You go to a lot of trouble.

    1. How many items to consider? 5 - A,B,C,D,E
    2. Highest value? Each of the items has an attribute called 'value'. Add 'em up. Which total is highest?
    3. Can we buy more than one? Legitimate question. A quick analysis of the data suggests values have been picked to make an obvious choice the wrong one (E C B adds up nicely to 25). One each seems to be indicated.

    Perhaps you are making the larger point about the continual headache of the professional: insufficiently detailed specifications. Or maybe I am just lacking in imagination.

    Dum Spiro Spero
      1. From the OP:

        (JFYI, I'm actually trying to write a salary cap script but I thought I'd give a simpler example).

        I don't think its unreasonable to consider the possibility that the OPs real problem could have substantially more items to be considered.

      2. Highest value?

        And you've never seen a case of a sloppy description here.

      3. Can we buy more than one? Legitimate question. A quick analysis of the data ...

        Is meaningless given the quote in 1. above. Please read my final paragraph.

      Or maybe I am just lacking in imagination.

      Or maybe you just didn't real the full question.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
      In the absence of evidence, opinion is indistinguishable from prejudice.

        If you're going to answer the question he should have asked instead of the one he did, you are of course free to include whatever complications your experience and imagination deem appropriate. And probably rightly so. As I said, I fault my own lack of imagination.

        Dum Spiro Spero
Re^2: maximizing value from a set of objects
by BrowserUk (Patriarch) on Nov 06, 2015 at 14:27 UTC

    BTW: If you use combinations() or combinations_with_repetition() instead of variations(), it cuts out the duplicates.