命令行子集总和

Question

我正在编写一个程序，该程序采用目标值和一组值列表，我需要从列表中选择将加起来等于目标值的数字。

这一切都必须在命令行上完成。

我陷入了两个部分:

首先，我不能 100% 确定我是否正确读取了所有值。因为在一些不应该匹配的测试中，它说存在匹配。

例如 子集2 100 1 2 3 4 找到组合匹配

它应该打印出没有找到匹配项，因为 1,2,3,4 加起来不等于 100。 我添加了代码来帮助您了解我在做什么

第二， 我需要打印列表中与目标值匹配的数字。我怎样才能做到这一点，我对如何做到这一点感到困惑。

例如 子集 9 1 2 4 5 {4,5}

#include <stdio.h>
#include <stdbool.h>

bool subset(int set[], int n, int sum);

int main(int argc, char *argv[])
{
    int value = atoi(argv[1]);

    // Error checking to see if the value is a negative
    if (value <= 0) {
        printf("Parameter 1 can not be negative\n");
        return -1;
    }

    int k;
    int t = 0;

    for (k = 2; k < argc; k++) {
        t++;
    }

    int i;
    int array = 0;

    /*
     * Putting the elements from the command line in an array starting
     * from the second element on the command line
     */

    for (i = 2; i < t; i++) {
        array += atoi(argv[i]);
    }

    int set[array];
    int n = sizeof(set) / sizeof(set[0]);

    // Call subset to check and see if there is a match
    if (subset(set, n, value) == true) {
        printf("Combination Match Found\n");
    } else {
        printf("No Combination Matches\n");
    }

    return 0;
}

// Returns true if there is a subset that equals the value
bool subset(int set[], int n, int sum)
{
    // Base cases
    if (sum == 0)
        return true;

    if (n == 0 && sum != 0)
        return false;

    // If last element is greater than sum, then its ignored
    if (set[n - 1] > sum)
        return (subset, n - 1, sum);

    // Check if value can be found with or without last element
    return subset(set, n - 1, sum) || subset(set, n - 1, sum - set[n - 1]);
}

Answer 1

我担心你有点乱。我将首先解决一些小问题。

int value = atoi(argv[1]);

如果你没有在命令行上输入任何参数，将会崩溃。您应该检查argc > 1首先。

for (k = 2; k < argc; k++) {
    t++;
}

可以这样写

t = argc - 2;

关于初始化set[]:

for (i = 2; i < t; i++) {
    array += atoi(argv[i]);
}

应该是

for (i=0; i<t; ++i) {
    set[i] = atoi(argv[i+2]));
}

set[] 是您的输入数组，对吗？它的长度应该是命令行参数的数量，对吗？如果我没看错的话，那么 set 的大小应该是 t，而不是 array。事实上，我没有看到您在计算后在任何地方使用 t 。 数组是输入值的总和；这对您有用吗(除了作为初步检查来看看问题是否可以解决)？

如果您想实际打印结果而不是测试是否可能，那么您将必须为结果分配一个数组，并对 subset() 进行一些重大更改.

我将创建另一个数组，名为result[]，其长度与set[]相同。我会将指向 result[] 的指针传递给 subset()，以及已填充的值的计数(初始值 0)。在 subset() 中，每当您从 set[] 获得一个可能的合法值时，请将其附加到 result[] 并递增长度。同样，在从 subset() 返回之前减少长度，有效地删除中间值。一旦 subset() 确定存在符合您的目标的合法值组合，该值列表就会被放置在 result[] 中。

这是家庭作业吗？如果是这样，我不愿意为您编写任何实际代码，但我希望我上面的描述有所帮助。

最后——这有点高级——你可能想对 memoization 做一些研究。和 dynamic programming作为此类问题的优化。