在游戏中可以做出的唯一得分是2,3,4,5,6,7,8,它们可制成任意次数访谈 - 甲骨文
什么是组合的总数球队可以参加比赛,并且可以通过球队达到50分。
例8,8,8,8,8,8,2有效8,8,8,8,8,4,4,2也有效。 etc ...
在游戏中可以做出的唯一得分是2,3,4,5,6,7,8,它们可制成任意次数访谈 - 甲骨文
什么是组合的总数球队可以参加比赛,并且可以通过球队达到50分。
例8,8,8,8,8,8,2有效8,8,8,8,8,4,4,2也有效。 etc ...
这看起来像一个硬币更换问题。我在一段时间后为它写了一些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
它就像访问一个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
结果中有重复项,因为2,2,...,3和2,3,2,... 2分开计数,这是不正确的,因为顺序并不重要。 – nhahtdh
这是更正后的版本:http://ideone.com/dxLHRd如果您选择了更高的分数,您将不会重新考虑分数。 – nhahtdh
嗯,我认为重复实际上是不同的方式,其中戏剧可以发生,以达到一个结果,所以他们应该没问题。根据问题的定义。 – user804979
的问题可以用动态规划来解决,有两个参数:
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)
看起来不错,但最下面的一行应该开始'f(i,s)= ...'(或者'score [i]'的两次出现都应该用'score [i + 1]'来代替)。 –
@j_random_hacker:谢谢。 – nhahtdh
只是偶然在这个问题上 - 这里是一个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个组合。
这与Java有什么特别的关系?你可以用任何语言解决这个问题。 – Makoto
这是带有2个参数的DP(当前总和,索引(最多考虑))。 – nhahtdh
@RavindraBagale - 这不是没有答案,因为它不是一个排列问题。 – user804979