如何利用的问题X数量，难度是总结Y元 [英] How to take X amount of questions, that sum up Y amount of difficulty

问题描述

我有一个表

问题 - >问题（串），难度（INT，1-10）

Questions -> Question(string), Difficulty (int, 1-10)

我需要创建一个方法，让我们从标题中提到，需要 X 问题金额，其难度要总结是。

I need to create a method, that as the title mentions, takes X amount of questions, whose difficulty should sum up Y.

例如：

getQuestions（2,10） - >问题1（差异：4），问题2（差异：6）

getQuestions(2,10) -> Question1 (diff: 4), Question2 (diff: 6)

getQuestions（3,15） - >问题3（差异：5），问题4（差异：5），Question5（差异：5）

getQuestions(3,15) -> Question3 (diff: 5), Question4 (diff: 5), Question5 (diff: 5)

我如何能够做到这样的事情LINQ的？

How can I achieve something like this with LINQ?

推荐答案

这里有一个办法做到这一点，使用递归解决方案的修改版本在这里找到：的Finding号码的所有可能的组合，以达到给定的总和

Here's one way to do it, using a modified version of the recursive solution found here: Finding all possible combinations of numbers to reach a given sum

首先，会做一些快速的验证，然后一个公共方法调用递归方法得到的结果：

First, a public method that will do some quick validation and then call a recursive method to get the results:

/// <summary>
/// Gets lists of numQuestions length of all combinations 
/// of questions whose difficulties add up to sumDifficulty
/// </summary>
/// <param name="questions">The list of questions to search</param>
/// <param name="numQuestions">The number of questions required</param>
/// <param name="sumDifficulty">The amount that the difficulties should sum to</param>
/// <returns></returns>
public static List<List<Question>> GetQuestions(List<Question> questions,
    int numQuestions, int sumDifficulty)
{
    if (questions == null) throw new ArgumentNullException("questions");

    var results = new List<List<Question>>();

    // Fail fast argument validation
    if (numQuestions < 1 || 
        numQuestions > questions.Count ||
        sumDifficulty < numQuestions * Question.MinDifficulty ||
        sumDifficulty > numQuestions * Question.MaxDifficulty)
    {
        return results;
    }

    // If we only need single questions, no need to do any recursion
    if (numQuestions == 1)
    {
        results.AddRange(questions.Where(q => q.Difficulty == sumDifficulty)
            .Select(q => new List<Question> {q}));

        return results;
    }

    // We can remove any questions who have a difficulty that's higher
    // than the sumDifficulty minus the number of questions plus one
    var candidateQuestions =
        questions.Where(q => q.Difficulty <= sumDifficulty - numQuestions + 1)
            .ToList();

    if (!candidateQuestions.Any())
    {
        return results;
    }

    GetSumsRecursively(candidateQuestions, sumDifficulty, new List<Question>(), 
        numQuestions, results);

    return results;
}

和则递归方法，做繁重的：

And then the recursive method that does the heavy lifting:

private static void GetSumsRecursively(IReadOnlyList<Question> questions, 
    int sumDifficulty, List<Question> candidates, int numQuestions, 
    ICollection<List<Question>> results)
{
    int candidateSum = candidates.Sum(x => x.Difficulty);

    if (candidateSum == sumDifficulty && candidates.Count == numQuestions)
    {
        results.Add(candidates);
    }

    if (candidateSum >= sumDifficulty)
        return;

    for (int i = 0; i < questions.Count; i++)
    {
        var remaining = new List<Question>();

        for (int j = i + 1; j < questions.Count; j++)
        {
            remaining.Add(questions[j]);
        }

        var filteredCandidates = new List<Question>(candidates) {questions[i]};

        GetSumsRecursively(remaining, sumDifficulty, filteredCandidates, 
            numQuestions, results);
    }
}

下面是一个例子用法：

public static void Main()
{
    const int numberOfQuestions = 3;
    const int sumOfDifficulty = 15;

    // Since I don't have your table, I'm using a list of objects to fake it
    var questions = new List<Question>();
    for (int i = 1; i < 11; i++)
    {
        questions.Add(new Question {Difficulty = i % 10 + 1, 
            QuestionString = "Question #" + i});
    }

    var results = GetQuestions(questions, numberOfQuestions, sumOfDifficulty);

    // Write output to console to verify results
    foreach (var result in results)
    {
        Console.WriteLine("{0} = {1}", string.Join(" + ", 
            result.Select(r => r.Difficulty)), sumOfDifficulty);
    }
}

和只是让你拥有一切，使这项工作，这里是用来假冒你的表我的问题类：

And just so you have everything to make this work, here's my Question class used to fake your table:

internal class Question
{
    public const int MinDifficulty = 1;
    public const int MaxDifficulty = 10;
    private int _difficulty;

    public int Difficulty
    {
        get { return _difficulty; }
        set
        {
            if (value < MinDifficulty) _difficulty = MinDifficulty;
            else if (value > MaxDifficulty) _difficulty = MaxDifficulty;
            else _difficulty = value;
        }
    }

    public string QuestionString { get; set; }
}

这篇关于如何利用的问题X数量，难度是总结Y元的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！