-1

I'm making a program that takes a target value and a set list of values, I need to pick numbers from the list that will add up to the target value.

This all has to be done on the command line.

Im stuck on two parts:

First is I'm not 100% sure if I'm reading in all the values correctly. Because on some tests where there shouldn't be a match it says there is a match.

For example subset2 100 1 2 3 4 Combination Match Found

It should print out instead no match found cause 1,2,3,4 dont add up to 100. I've added my code to help you see what im doing

Second, I need to print out the numbers in the list that do match with the target value. How would I be able to do that, I'm stumped on how i could do this.

For example subset 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]);
}
4

2 回答 2

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

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

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

    if (value <= 0) {
        printf("Parameter 1 must be positive\n");
        return -1;
    }

    int array_size = argc - 2;
    int set[array_size];
    for(int i=0;i<array_size;++i)
        set[i] = atoi(argv[2 + i]);

    // Call subset to check and see if there is a match
    if (subset(set, array_size, 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 target_sum){
    if (target_sum == 0){
        printf("{ }\n");
        return true;
    }
    if (n == 0 && target_sum != 0)
        return false;

    unsigned limit = 1 << n;
    int wk[n];
    for(unsigned i=1;i < limit; ++i){
        int k = 0, sum = 0;
        unsigned x = i;
        for(int j = 0; x ; ++j, x>>=1){
            if(x & 1){
                sum += (wk[k++] = set[j]);
                if(sum  > target_sum) break;
            }
        }
        if(sum == target_sum){
            printf("{ ");
            for(int j = 0;j<k;++j)
                printf("%d ", wk[j]);
            printf("}\n");
            return true;
        }
    }
    return false;
}
于 2013-05-23T23:34:58.270 回答
0

恐怕你到处都是。我先解决几个小问题。

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[].

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

最后——这有点高级——你可能想对记忆化和动态编程做一些研究，作为这类问题的优化。

于 2013-05-23T20:59:56.797 回答