0

I have an array in the format:

$array = array(
    0 => array(
        'name' => 'Item 1',
        'level' => 1,
        'points' => 10
    ),
    1 => array(
        'name' => 'Item 1',
        'level' => 2,
        'points' => 12
    ),
    ...
    24 => array(
        'name' => 'Item 1',
        'level' => 25,
        'points' => 100
    ),
    25 => array(
        'name' => 'Item 2',
        'level' => 1,
        'points' => 10
    ),
    26 => array(
        'name' => 'Item 2',
        'level' => 2,
        'points' => 12            
    ),
    ...
    34 => array(
        'name' => 'Item 2',
        'level' => 10,
        'points' => 30            
    ),
    ...
    97 => array(
        'name' => 'Item 10',
        'level' => 1,
        'points' => 14
    ), 
    ...       
    108 => array(
        'name' => 'Item 10',
        'level' => 12,
        'points' => 200
    ),
    ...
    324 => array(...)
);

From the above, please infer:

  1. Each "Item" has varying levels, for example, "Item 1" has 24 levels, but some Items can have up to 30 levels.
  2. Points are not incremental or derived by a (known) formula.
  3. There are 324 total "Items" lines in the reference data (18 Items with varying levels).

The user will input a point number of, say 8000, and this data array need to somehow give me a list of combinations of at most one of each "Item", but not necessarily one of each "Item" where the sum of points for these "Items" add up to exactly 8000 points.

The only way I can think of is to make a sort-of rainbow table with point values in it for each possible combinations, as an attempt at recursion made my machine ran out of memory.

For your reference, the number of levels for the 18 "Items" (in no particular order) are:

30, 25, 20, 15, 1, 1, 3, 1, 3, 20, 25, 30, 30, 30, 30, 30, 20, 10 = 324 Levels.

I am not sure of the math, but I think there will be 30 * 25 * 20 ... * 20 * 10 rows in the table, so not sure that is feasible or possible.

How would I tackle this problem to get a result (if any) that matches user's input points?

5
  • 1
    If I'm reading this right, this sounds like the subset sum problem. Do the solutions on that wikipedia page help?
    – Ixrec
    May 21 '16 at 20:36
  • Hi @lxrec! Thanks! I have skimmed through your article reference... It sure seems like what I am dealing with. The math behind it is way over my head, but I will definitely have to research that further; which I can, now that I know what it is called. Once I understand it, I can try and implement it programmatically. Thanks! No idea how to start, but at least I know where :-) May 22 '16 at 13:03
  • 1
    Glad I could help. If you hit a specific roadblock (before anyone posts an answer here), please edit your question to focus on that and then we can provide some more useful advice. The main reason no one's answered so far is that we probably can't add anything to what that wikipedia article already says, but we can definitely help with clarifying pieces of it or details it doesn't cover very well.
    – Ixrec
    May 22 '16 at 13:35
  • Hi @lxrec! You definitely got me on the right track, but I am afraid that this problem cannot be solved, really, because I do not have the hardware capable to handling these sheer numbers. I guess there is a reason why nobody ever published this tool for the online game I am playing; because it is infeasible to do this. I will upvote your comment, but I am abandoning the question. It is a good question though, and hence I do not want to delete it. Or should I? Someone might come up with something, sometime? Thoughts? May 25 '16 at 11:11
  • At the moment, as far as I know this question is effectively asking "How do I solve the subset sum problem?" which is thoroughly answered elsewhere and thus not of any great value here even though the topic is important. But it is on-topic and a far better question than most of the junk we get every day, so I don't see any real need to delete it. So I guess leave it as-is for now.
    – Ixrec
    May 25 '16 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.