void printSum(double candidates[], int index[], int n)
{
        for (int i = 0; i < n; i++)
                cout << candidates[index[i]] << " ";
        cout << endl;
}

void getsum_help(double target, double sum, double candidates[], int size, int index[], int n)
{
        if (sum > target)
                return;
        if (fabs(sum-target) <= 1e-6*fabs(target))
                printSum(candidates, index, n);
        int starti = n==0 ? 0 : index[n-1]+1;
        for (int i = starti; i < size; i++)
        {
                index[n] = i;
                getsum_help(target, sum + candidates[i], candidates, size, index, n+1);
        }
}

void getsum(double target, double candidates[], int size)
{
        int *index = new int[size];
        getsum_help(target, 0, candidates, size, index, 0);
        delete []index;
}

原帖由 阿尔法孝直 于 2010-11-30 12:11 发表


我觉得题目表达有点奇怪：
按照出题的原意，似乎应该是：

有n种商品，单价分别为：
v1, v2, v3, v4, ..., vn
有现金m元，求解是否可以从n种商品中，每种选择若干件，总价正好为m元。

不过现在的题 ...