How to calculate the sum of dice whose value combined amounts to an input number

Question

I am supposed to do a score calculator in Java for a dice game that rolls 6 dice (with 6 faces). The score is supposed to be calculated according to a list of options that the user has available. Options are 4,5,...,12. For choice "4", all combinations of dice whose values amount to 4 give points.

Each dice can be selected only once during scoring. It doesn't matter which dice are grouped together as long as their sum is equal to the choice value and the total value of the points is maximised. So for example the roll {1 2 4 2 3 3} gives 12 points if user chooses option "4" ([1 3]+[4]+[2 2]). 11 points ([4 3 3 1]) if user chooses option "11". 12 points if user chooses option "6".

I've tried several ways of calculating this but none gives me correct results in 100% of the cases and I've now been stuck with this for over a day.

My question is what would be a good solution/algorithm int calc(List<Integer> input, int sum) such that e.g.

calc({6,6,6,6,6,5}, 12)=24
calc({6,6,6,6,6,5}, 11)=11
calc({6,6,6,6,6,5}, 3)=0
calc({6,6,6,6,6,5}, 6)=30

Help much appreciated.

Answer 1

This is a combinatoric search problem. Here is the recursive algorithm which examines the entire search space. dice is a sequence of integers (each a number between 1 and 6), target is the number 4 .. 12 chosen by the player, and best is the best sum of previously totaled die (initially 0):

score(target, dice, best=0) {
    hi = best;
    for all subsets S of dice 
       if sum S = target
           val = score(target, dice - S, best + target)
           if val > hi
              hi = val;
    return hi;
}

And here is my Java implementation (I am a little rusty with Java):

import java.util.Vector;

public class DiceGame {
    public int targetSum;

    public DiceGame(int t) {targetSum = t;}

    public int sumOfDice(Vector<Integer> dice) {
        int s = 0;
        for (int d : dice)
            s += d;
        return s;
    }

    public int score(Vector<Integer> dice) {
        return score(dice, 0);
    }

    public int score(Vector<Integer> dice, int bestPrev) {
        int hi = bestPrev;
        for (int n = 1; n < (1 << dice.size()); n++) {
            Vector<Integer> subset = new Vector<Integer>();
            Vector<Integer> remaining = new Vector<Integer>();
            for (int i = 0; i < dice.size(); i++) {
                if ((n & (1 << i)) != 0)
                    subset.add(dice.get(i));
                else
                    remaining.add(dice.get(i));
            }
            if (sumOfDice(subset) == targetSum) {
                int s = score(remaining, bestPrev + targetSum);
                if (s > hi)
                    hi = s;
            }
        }
        return hi;
    }

    public static void main(String[] args) {
        Vector<Integer> dice = new Vector<Integer>();
        // 4 2 4 2 2 6
        dice.add(4);
        dice.add(2);
        dice.add(4);
        dice.add(2);
        dice.add(2);
        dice.add(6);
        DiceGame diceGame = new DiceGame(6);
        int s = diceGame.score(dice);
        System.out.println(s);
    }
}

And here is my thorough test :)

$ java DiceGame
18

Note: I used score/target where you used calc/sum and I used Vector where you used List .. I'll let you write the proper adapter,