c# - 复杂的递归函数 - 在房间和人员之间分配星星

Question

假设我的星星总数为 n，有多个房间，每个房间最多可容纳 3 人。我想知道在一个人最多可以拥有 7 颗星的情况下，我可以分配多少种星星组合。

例如，我总共有 4 颗星。一种可能的解决方案是:

room: person *
room: person *
room: person *
room: person *

another possible is
room: person ****

another just in case is
room: person* person* person*
room: person *

public class SolutionData
{
        public class PackData
        {
            public List< int > people; // number of stars
            public PackData( )
            {
                people= new List<int>( );
            }
        }

        public List< PackData > packs;

        public SolutionData( )
        {
            packs = new List< PackData >( );
        }
}

有什么方法可以填充包含所有可能性的解决方案数据数组吗？

我有什么

static void GetSolutions( int totalRank , ref List< SolutionData > solutions )
{
    if( totalRank == 0 ) return;

    if( totalRank >= 1 ) GetSolutions( totalRank - 1 , ref solutions );
    if( totalRank >= 2 ) GetSolutions( totalRank - 2 , ref solutions );
    if( totalRank >= 3 ) GetSolutions( totalRank - 3 , ref solutions );
    if( totalRank >= 4 ) GetSolutions( totalRank - 4 , ref solutions );
    if( totalRank >= 5 ) GetSolutions( totalRank - 5 , ref solutions );
    if( totalRank >= 6 ) GetSolutions( totalRank - 6 , ref solutions );
    if( totalRank >= 7 ) GetSolutions( totalRank - 7 , ref solutions );
}

有时我必须填写解决方案，但我真的不知道在哪里以及如何填写。我什至不知道部分功能是否正确。

注意:房间/包没有限制，显然最大数量是总星星数n。总星星数 n 不会很高，最多 20-30。

Answer 1

Is there any way I can fill an array of solutionData containing all the possiblities?

我不会采用这种方法。如果目标是创建一组组合，则返回一组组合。不要获取一个数组并填充它。方法中包含什么？星星的数量。出来什么？组合的集合。该方法应具有签名:

static IEnumerable<SolutionData> GetSolutions(int totalRank)

您希望创建一个递归解决方案，并且您有一个递归解决方案的草图:

• 您有一个简单的基本案例。您似乎有一个零星的解决方案 - 也就是说，没有解决方案 - 但这可能没有那么有帮助。 给定零颗星的解决方案，您能否构建一颗星的解决方案？这就是你需要做的。如果你做不到这一点，那么基本情况必须是一颗星，而不是零。

• 简化为较小问题的递归情况。假设您寻求 10 颗星的解决方案，并且您已经有了 9 颗星的解决方案。你能用 9 星的解来构造 10 星的解吗？如果不是，那么该算法就不会是递归的。现在概括一下；如果您有 n-1 颗星的解决方案，您可以根据该信息创建一个解决方案来解决 n 颗星的问题吗？

所以你的方法将具有以下形式:

if (in the base case)
    return the trivial solution
else
    solve a smaller problem recursively
    construct the solution to the larger problem from that solution
    return the solution

你似乎在这里失败的地方是在给定较小问题的解决方案的情况下生成新的解决方案。专注于此。假设您希望解决 10 的问题，而在这里，我会神奇地为您提供 9 的解决方案。您将如何利用这些信息来发挥优势？

现在，一旦你做到了，它可能会太慢而不可行。评论中提到了动态规划，即以下技术:

if (in the base case)
    return the trivial solution
else if (we have solved this problem before and remember the solution)
     return the previous solution
else
    solve a smaller problem recursively
    construct the solution to the larger problem from that solution
    make a note in global state of the solution to this problem
    return the solution

动态编程的思想是，许多递归算法花费大量时间来重新解决几纳秒前已经解决的问题。如果您消耗额外的内存来记住解决方案，则可以节省重新计算它们的时间。