Fruit Baskets 解题报告 Kattis 暴力求解法

题意：
题目中说了很多废话。其实就是解决一个问题：
给出m个不同质量的物体，并且每个物体的质量大于等于50，
问你在这m个物体中随便取（可以取1个，2个，3个等等），满足取出来的物体的质量和大于200的质量和。
比如给你：
50 60 200
大于200的组合有：
50 200
60 200
50 60 200
对应：
输出 （50+200） + （60 + 200）+（50 + 60 + 200） = 820
即 820
解题思路：
如果枚举：每个重量的物体取或者不取那么就是2的n次方，n为不同质量的种类数。
下面给出一个多项式时间的解决方法：
首先：
注意：如果物体数目大于等于4 任意大于等于4的组合一定满足
这是因为每个物体不少于50。那么我们按照种类数目分类：
1.如果给出的数目小于4:那么直接全排列看看只要产生的组合之和大于200就加上。
2.如果给出的数目大于等于4:
从所有情况减去不符合要求的情况：
总的情况一定是每个质量被选取了 2^(n-1)次 所以出现了2^(n-1)次。对于所有物体就是每个物体质量*2^(n-1)再求和。
不满足情况的一定是存在于那些组合中物体数小于等于3的之中。

那么最后的结果一定是 总的 - 不合情况的
3.需要注意的是使用位运算的要加LL不然直接>>1会溢出。

代码实现

#include <iostream>
#include <cmath>
using namespace std;
int con[42];
long long  sum = 0; int  n;
void zuhe(int a[], int n, int m, int flag)
{   //p[x]=y 取到的第x个元素，是a中的第y个元素
    int index, i, *p;
    p = (int*)malloc(sizeof(int) * m);
    index = 0;
    p[index] = 0; //取第一个元素
    while (true)
    {
        if (p[index] >= n)
        {   //取到底了，回退
            if (index == 0)
            {   //各种情况取完了，不能再回退了
                break;
            }
            index--;//回退到前一个
            p[index]++;//替换元素
        }
        else if (index == m - 1)
        {   //取够了，输出
            int res = 0;
            for (i = 0; i < m; i++)
            {
                res += a[p[i]];
            }
            if (flag == 1)
            {
                if (res >= 200)
                {
                    sum += res;

                }
            } else {
                if (res < 200)
                {
                    sum -= res;
                }
            }

            p[index]++; //替换元素
        }
        else
        {   //多取一个元素
            index++;
            p[index] = p[index - 1] + 1;
        }

    }
}
int main(int argc, char const * argv[])
{
    scanf("%d", &n);
    int tempsum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &con[i]);
        tempsum += con[i];
    }
    if (tempsum < 200)
    {
        printf("0\n");
        return 0;
    } else if (tempsum == 200)
    {
        printf("200\n");
        return 0;
    }
    if (n < 4)
    {
        for (int i = 1; i <= n; i++)
        {
            zuhe(con, n, i, 1);
        }
    } else {
        sum += tempsum*pow(2,n - 1);
        for (int i = 1; i <= 3; i++)
        {
            zuhe(con, n, i, 0);
        }
    }
    printf("%lld\n", sum);
    return 0;
}