算法 - 在给定特定值的情况下查找掷出的骰子中的最大组合数

Question

假设我有 6 个骰子，我掷骰子，然后得到以下结果：1,1,1,2,4,4，我想知道我可以做出多少种可能的组合，总和为 5。我可以做 1 +1+1+2 这将给我 1 种可能的组合，因为所使用的骰子将被排除。或者我可以做 1+4 和 1+4 来得到 2 种组合。有什么数学公式或算法可以帮助我实现这个目标吗？如果能简短解释一下所提供的方法为何有效，我们将不胜感激。

Answer 1

我认为不存在封闭式解决方案，但存在一个循环公式。对于每个骰子提名 D，如果有 nd 个骰子可用，我们可以将其简化为较小问题的解决方案之和，取这些骰子中的 0..nd。

概念实现，Python：

from collections import Counter, defaultdict

def n_combinations(target_sum, dice):
    dp = {target_sum: 1}
    for dice_value, values_available in Counter(dice).items():
        new_dp = defaultdict(int)
        for count in range(values_available+1):
            for remaining_target, nways in dp.items():
                new_target = remaining_target - dice_value*count
                if new_target >= 0:
                    new_dp[new_target] += nways
        dp = new_dp
    return dp[0]

# returns 2
n_combinations(5, [1,1,1,2,4,4])