java - 如何计算其值总和等于输入数字的骰子总和

Question

我应该用 Java 为掷 6 个骰子(有 6 个面)的骰子游戏做一个分数计算器。分数应该根据用户可用的选项列表来计算。选项为 4,5,...,12。对于选项“4”，所有点数等于 4 的骰子组合都给分。

每个骰子在计分过程中只能选择一次。将哪些骰子组合在一起并不重要，只要它们的总和等于选择值并且点的总值最大化即可。因此，例如，如果用户选择选项“4”([1 3]+[4]+[2 2])，掷骰 {1 2 4 2 3 3} 将得到 12 分。 11 分 ([4 3 3 1]) 如果用户选择选项“11”。如果用户选择选项“6”，则为 12 分。

我已经尝试了几种计算方法，但没有一种方法在 100% 的情况下给我正确的结果，我现在已经坚持了一天多。

我的问题是什么是好的解决方案/算法 int calc(List<Integer> input, int sum)例如

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

非常感谢帮助。

Answer 1

这是一个组合搜索问题。这是检查整个搜索空间的递归算法。 dice 是一个整数序列(每个都是 1 到 6 之间的数字)，target 是玩家选择的数字 4 .. 12，best 是先前合计的 die 的最佳总和(最初为 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;
}

这是我的 Java 实现(我对 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);
    }
}

这是我的全面测试:)

$ java DiceGame
18

注意:我使用了score/target，你使用了calc/sum，而我使用了 Vector 你使用 List 的地方..我会让你写合适的适配器，