面试 - Oracle

Question

在这个游戏中，可以得分的分数只有2、3、4、5、6、7、8，它们可以无限次地获得。要求团队达到50分，问有多少种组合方式可以实现。

例如，8,8,8,8,8,8,2是有效的，8,8,8,8,8,4,4,2也是有效的，等等...

- user804979

---

这与Java有什么特别关系吗？你可以用任何编程语言来解决这个问题。 - Makoto

这是带有两个参数的DP（当前总和，已考虑的索引）。 - nhahtdh

@RavindraBagale - 不，那不是答案，因为它不是一个排列问题。 - user804979

动态规划，我同意这一点。但是你要维护哪种缓存，你会维护所有组合的缓存以确保不重复它们与下一个索引...或者您可以解释一下您将维护的状态以更好地理解您的答案。 - user804979

请澄清您是否希望顺序具有重要意义（例如，8、8、8、8、8、8、2与8、8、8、8、8、2、8是否不同？） - j_random_hacker

可能是[DP-找零钱问题]的重复问题。(http://stackoverflow.com/questions/11861038/dp-counting-coin-change) - Raymond Chen

Answer 1

问题可以通过动态规划解决，有两个参数：

- `i` - 我们已经考虑的索引。 - `s` - 总分数。

`f(i, s)` 将包含实现得分 `s` 的总方法数。

让 `score[]` 成为可以制作的唯一正分数列表。

DP解决方案的公式：

f(0, s) = 1, for all s divisible to score[0]
f(0, s) = 0, otherwise

f(i + 1, s) = Sum [for k = 0 .. floor(s/score[i + 1])] f(i, s - score[i + 1] * k)

- nhahtdh

---

看起来不错，但是底部一行应该以 f(i, s) = ... 开始（或者将 score[i] 的两个出现替换为 score[i + 1]）。 - j_random_hacker

Answer 2

这看起来像是一个硬币找零问题。我之前写过一些Python代码。

修改后的解决方案：

from collections import defaultdict

my_dicto = defaultdict(dict)

def row_analysis(v, my_dicto, coins):
    temp = 0
    for coin in coins:
        if v >= coin:
            if v - coin == 0: # changed from if v - coin in (0, 1):
                temp += 1
                my_dicto[coin][v] = temp
            else:                
                temp += my_dicto[coin][v - coin]
                my_dicto[coin][v] = temp
        else:
            my_dicto[coin][v] = temp
    return my_dicto

def get_combs(coins, value):
    '''
    Returns answer for coin change type problems.
    Coins are assumed to be sorted.

    Example:
        >>> get_combs([1,2,3,5,10,15,20], 50)
        2955
    '''
    dicto = defaultdict(dict)

    for v in xrange(value + 1):
        dicto = row_analysis(v, dicto, coins)

    return dicto[coins[-1]][value]

在您的情况下：

>>> get_combs([2,3,4,5,6,7,8], 50)
3095

- Akavall

---

@nhahtdh，谢谢你。让我看看我能不能快速解决这个问题。 - Akavall

@nhahtdh，我想我解决了它。我的解决方案也改变了原始问题，所以再次感谢你。 - Akavall

Answer 3

这就像访问一个有7个分支的决策树。

代码如下：

class WinScore{
static final int totalScore=50;
static final int[] list={2,3,4,5,6,7,8};
public static int methodNum=0;

static void visitTree( int achieved , int index){
        if (achieved >= totalScore ){
                return;
        }
        for ( int i=index; i< list.length; i++ ){
                if ( achieved + list[i] == totalScore ) {
                        methodNum++;
                }else if (  achieved + list[i] < totalScore ){
                        visitTree( achieved + list[i], i );
                }
        }
}
public static void main( String[] args ){
        visitTree(0, 0);
        System.out.println("number of methods are:" + methodNum );

}
}
output:
number of methods are:3095

- Richard

---

你的结果中存在重复，因为2,2,...,3和2,3,2,...2被分别计算了两次，这是不正确的，因为顺序并不重要。 - nhahtdh

这是已更正的版本: http://ideone.com/dxLHRd 如果你已经选择了更高的分数，就不会重新考虑评分。 - nhahtdh

@user804979：你应该明确这一点，因为解决方案可能会有所不同。 - nhahtdh

@nhahtdh：我认为数字可以重复任意次数并以任何顺序出现。你能澄清一下吗？如果总分是7，可能的答案是什么？我认为有7种方法：{2,2,3}，{2,3,2}，{2,5}，{3,2,2}，{3,4}，{5,2}，{7}。 - Richard

你需要考虑顺序，所以2,2,3和2,3,2是不同的。而我认为它们是相同的，只计算一次。实际上，这个问题要求的是组合数，而不是排列数，因此不应考虑顺序。 - nhahtdh

Answer 4

我刚偶然看到这个问题 - 这里是一个允许你探索不同组合的c#变体：

static class SlotIterator
{
    public static IEnumerable<string> Discover(this int[] set, int maxScore)
    {
        var st = new Stack<Slot>();
        var combinations = 0;
        set = set.OrderBy(c => c).ToArray();
        st.Push(new Slot(0, 0, set.Length));
        while (st.Count > 0)
        {
            var m = st.Pop();
            for (var i = m.Index; i < set.Length; i++)
            {
                if (m.Counter + set[i] < maxScore)
                {
                    st.Push(m.Clone(m.Counter + set[i], i));
                }
                else if (m.Counter + set[i] == maxScore)
                {
                    m.SetSlot(i);
                    yield return m.Slots.PrintSlots(set, ++combinations, maxScore);

                }
            }
        }
    }

    public static string PrintSlots(this int[] slots, int[] set, int numVariation, int maxScore)
    {
        var sb = new StringBuilder();
        var accumulate = 0;
        for (var j = 0; j < slots.Length; j++)
        {
            if (slots[j] <= 0)
            {
                continue;
            }
            var plus = "+";
            for (var k = 0; k < slots[j]; k++)
            {
                accumulate += set[j];
                if (accumulate == maxScore) plus = "";
                sb.AppendFormat("{0}{1}", set[j], plus);
            }
        }

        sb.AppendFormat("={0} - Variation nr. {1}", accumulate, numVariation);
        return sb.ToString();
    }
}
public class Slot
{
    public Slot(int counter, int index, int countSlots)
    {
        this.Slots = new int[countSlots];
        this.Counter = counter;
        this.Index = index;
    }

    public void SetSlot(int index)
    {
        this.Slots[index]++;
    }

    public Slot Clone(int newval, int index)
    {
        var s = new Slot(newval, index, this.Slots.Length);
        this.Slots.CopyTo(s.Slots, 0);
        s.SetSlot(index);
        return s;
    }

    public int[] Slots { get; private set; }

    public int Counter { get; set; }

    public int Index { get; set; }
}

例子：

    static void Main(string[] args)
    {

        using (var sw = new StreamWriter(@"c:\test\comb50.txt"))
        {
            foreach (var s in new[] { 2, 3, 4, 5, 6, 7, 8 }.Discover(50))
            {
                sw.WriteLine(s);
            }
        }
    }

共有3095种组合。

- Anthill