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

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 分。

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

我的问题是什么是好的 solution/algorithm 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

这是一个组合搜索问题。这是检查整个搜索 space 的递归算法。 dice 是一个整数序列（每个整数在 1 到 6 之间），target 是玩家选择的数字 4 .. 12，best 是先前总和的最佳总和死亡（最初为 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 .. 我会让你写合适的适配器，

Answer 2

我们可以设想的一个状态是，当我们迭代输入时，每个“选项”（从 1 到 12 的总和）有多少。这是一种递归方法，它尝试将当前骰子与不同的总和相加，以查看哪个胜出。

状态（和 return 值）是一个数组，其中第一个元素是可实现的最大总和，其余元素是总和等于其在数组中的索引的计数（只有总计为最大值是相关的）。

JavaScript 代码（鉴于限制，记忆似乎没有必要）：

function f(dice){
  function g(i, state){
    if (i == dice.length)
      return state;
      
    const die = dice[i];
      
    // Increment number of die parts
    const _state = state.slice();
    _state[die] += 1;
    _state[0] = Math.max(_state[0], _state[die] * die);
    let best = g(i + 1, _state);
    
    // Try adding die to other sums
    for (let j=1; j<=12-die; j++){
      if (state[j]){
        const _state = state.slice();
        const sum = j + die;
        _state[j] -= 1;
        _state[sum] += 1;
        _state[0] = Math.max(
          _state[0], _state[sum] * sum);
        const next = g(i + 1, _state);
        if (next[0] > best[0])
          best = next;
      }
    }
    
    return best;
  }
  
  return g(0, new Array(13).fill(0));
}

var games = [
  [1, 2, 4, 2, 3, 3],
  [4, 2, 4, 2, 2, 6],
  [6, 6, 6, 6, 6, 5]
];

for (let dice of games){
  console.log(JSON.stringify(dice));
  console.log(JSON.stringify(f(dice)));
  console.log('');
}

要找到特定目标的最大值，我们可以调整比较的最大值：

function f(dice, t){
  function g(i, state){
    if (i == dice.length)
      return state;
      
    const die = dice[i];
      
    // Increment number of die parts
    const _state = state.slice();
    _state[die] += 1;
    _state[0] = Math.max(_state[0], _state[t] * t);
    let best = g(i + 1, _state);
    
    // Try adding die to other sums
    for (let j=1; j<=12-die; j++){
      if (state[j]){
        const _state = state.slice();
        const sum = j + die;
        _state[j] -= 1;
        _state[sum] += 1;
        _state[0] = Math.max(
          _state[0], _state[t] * t);
        const next = g(i + 1, _state);
        if (next[0] > best[0])
          best = next;
      }
    }
    
    return best;
  }
  
  return g(0, new Array(13).fill(0));
}

var games = [
  [[1, 2, 4, 2, 3, 3], 4],
  [[4, 2, 4, 2, 2, 6], 6],
  [[6, 6, 6, 6, 6, 5], 3]
];

for (let [dice, t] of games){
  console.log(JSON.stringify(dice, t) + " " + t);
  console.log(JSON.stringify(f(dice, t)));
  console.log('');
}

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

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

java

algorithm

dice