c# - 组合总和

Question

我有一个像 {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8} 这样的数组，其中每个整数代表百分比。数字的目标总和应该是 100%，但由于它们已四舍五入到最接近的整数(向上舍入 .5)，因此总和可能不是 100。我需要知道四舍五入前的实际值是否总和可以达到 100%

我尝试过的:我认为数组中的值可以是向上舍入的结果，在这种情况下原始值将小于 0.5，或者该值可以是向下舍入的结果，在这种情况下原始值将大于 0.4。所以我尝试了这个，知道差异(例如从上面的例子)是 7，是否存在 X*(-0.5) + Y*0.4 的某种组合，其中 X 和 Y 是常数，其总和 = 计算数组的长度，那会让我相差7？这种策略适用于一些测试用例，例如 {12,12,12,12,12,12,12,12} 和 {13,13,13,13,13,13,13,13} 但根据这个还不行对于答案，可以使这个数组的目标总和为 100%，因此我的函数应该返回 true。

这是我试过的代码。

Boolean combination(int difference, int count)
{
    decimal d;
    for (int x = 0; x <= count;x++)
    {
        for(int y=0; y<=count-x;y++)
        {
            d = (x * (decimal)(-0.5)) + (y * (decimal)(0.4));
            if ( d == difference)
                return true;
        }
    }

    return false;
}

原创练习题，来自topcoder.com SRM 544 DIV 2； > 700 次提交的成功率 < 20%。我猜这是一个棘手的问题:)

在正常选举中，人们期望每位候选人获得的百分比加起来恰好为 100%。有两种情况可能不是这种情况:如果选举存在欺诈，或者报告的百分比是四舍五入的。在最近的一次选举中，已知选民人数恰好是 10000。假设选举是公平进行的，每个选民只投给了一名候选人。在报告之前，每位候选人获得的选票百分比四舍五入到最接近的整数。位于两个连续整数中间的百分比被四舍五入。投票部正在寻找选举舞弊的证据。你会得到一个 int[] percentages，给出每个候选人所报告的选票百分比。如果选举肯定是欺诈性的，则返回包含“YES”的字符串，否则返回“NO”(引号只是为了清楚起见)。也就是说，如果 10000 名选民中的每一个都不能恰好投票给一名候选人，则返回“YES”，否则返回“NO”。

感谢任何帮助我的人。请不要发布对此的所有答案，我所要求的只是我可能没有考虑过的新思路。

Answer 1

假设我们有一组整数 { N1, N2, N3 } 。

原数最少能达到多少和？

它是{ N1-0.5, N2-0.5, N3-0.5 } 数组中元素的总和，我们可以改写为:

sum({ N1, N2, N3}) - 0.5 * count({ N1, N2, N3 })

最小金额必须小于或等于到100。

原数最多能达到多少和？

是{N1+0.4999...,N2+0.4999...,N3+0.4999...}数组中元素的和，我们可以改写为:

sum({ N1, N2, N3}) + 0.4999... * count({ N1, N2, N3 })

最大总和必须或等于100。

我们不想处理 0.499... 所以我们可以将其重写为:

sum({ N1, N2, N3}) + 0.5 * count({ N1, N2, N3 })

但在这种情况下，它不能等于到100，即它必须严格大于100>.

所以我们可以用C#编写如下代码:

static bool CanSumTo100(IList<int> numbers)
{
    return numbers.Sum() - 0.5 * numbers.Count <= 100 &&
           numbers.Sum() + 0.5 * numbers.Count > 100;
}

如果不想处理 float ，可以使用整数:

static bool CanSumTo100(IList<int> numbers)
{
    int sum = numbers.Sum();
    int count = numbers.Count;
    return 2 * sum - count <= 200 &&
           2 * sum + count > 200;
}