how to write this program

[mamali]

i want to write a program that gives 40 numbers and another number named "k" and found is there any subset that sums "k".
could any one help me ?

[elvenspike]

im not sure what you're asking here. is 'k' a variable? can you be a bit clearer?

[mamali]

yes 'k' is a variable name .
for example i do it for 5 numbers :
1 2 3 4 5
k:6
and the out put must be "yes" because 1 + 2 + 3 and 1 + 5 and 2+4 equals 6
now i dont know how to write it with 40 numbers

[jsmith]

Look up the knapsack problem.

The best known approach is brute force check all combinations.

[jLNv0pDG]

My attempt at this: http://pastebin.com/m57fdaecf

Does that seem like a workable or understandable piece of code? I thought my binary-array method for constructing subsets was kinda clever. I'd appreciate any constructive criticism or comments you guys may have. :)

[elvenspike]

an easy way would be using a for statement and variables. use the for statement to have it repeat until the values are >= the variable k and just have it increase the variables. you might have to play around with it a bit if you really want it done, i can show you what i'd personall do in this situation if you want.

[jLNv0pDG]

I'd love to see what you or anyone else would do in this situation.

[jsmith]

Well, going for brevity:

#include <algorithm>
#include <boost/lexical_cast.hpp>
#include <iostream>
#include <string>

void Run( int target, const std::string& str, int sum, const int* first, const int* last )
{
    for( ; first != last; ++first )
        if( sum + *first == target )
            std::cout << str << ( str.empty() ? "" : " + " ) << *first 
                << " = " << target << std::endl;
        else if( sum + *first < target )
            Run( target, str + ( str.empty() ? "" : " + " ) + 
                boost::lexical_cast<std::string>( *first ),
                sum + *first, first + 1, last );
}

int main() {
    int nums[40] = { 
      103, 107, 109, 113, 117, 119, 127, 131, 133, 137,
        1,   2,   3,   5,   7,  11,  13,  17,  19,  23,  
       67,  71,  73,  79,  83,  87,  89,  91,  97, 101,
       29,  31,  37,  41,  43,  47,  51,  53,  59,  61
    };
    
    std::sort( &nums[0], &nums[40] );
    Run( 50, std::string(), 0, &nums[0], &nums[40] );
}

is the shortest I can think of.

[elvenspike]

gimmie a few minutes, i might be able to get something that looks cleaner than jsmith's. no offense to you, i just hate the way "std::" looks.

[jsmith]

#include <algorithm>
#include <boost/lexical_cast.hpp>
#include <iostream>
#include <string>

using boost::lexical_cast;
using std::cout;
using std::endl;
using std::sort;
using std::string;

void Run( int target, const string& str, int sum, const int* first, const int* last )
{
    for( ; first != last; ++first )
        if( sum + *first == target )
            cout << str << ( str.empty() ? "" : " + " ) << *first 
                << " = " << target << endl;
        else if( sum + *first < target )
            Run( target, str + ( str.empty() ? "" : " + " ) + 
                lexical_cast<string>( *first ), sum + *first, first + 1, last );
}

int main() {
    int nums[40] = { 
      103, 107, 109, 113, 117, 119, 127, 131, 133, 137,
        1,   2,   3,   5,   7,  11,  13,  17,  19,  23,  
       67,  71,  73,  79,  83,  87,  89,  91,  97, 101,
       29,  31,  37,  41,  43,  47,  51,  53,  59,  61
    };
    
    sort( &nums[0], &nums[40] );
    Run( 50, string(), 0, &nums[0], &nums[40] );
}

More lines this way...

[elvenspike]

going with simplicity over brevity, here's my code :

#include <iostream>
using namespace std;

void FUNCT(int a, int b);

int main() {
	int a, b; // a is num to compare 1, b is num to compare 2
	a = 1;
	b = 2;
	FUNCT(a,b);
	return 0;
}

void FUNCT(int a, int b) {
	int c; // the output variable o.o
	int d;
	d = a+b;
	if (d == 3) {
		c = 1;
	} else {
		c = 0;
	}
	cout << "[ " << a << " + " << b << " = 3 ] is ";
	if ( c == 1 ) {
		cout << "true.\n";
	} else {
		cout << "false.\n";
	}
}

all you'd have to do is :
change the comparison to the number max you desire AND
use a for statement to change the values or do it the way i did it repeatedly.

[jLNv0pDG]

#include <boost/lexical_cast.hpp>

...

d:\c++ projects\test2.cc(2) : fatal error C1083: Cannot open include
 file: 'boost/lexical_cast.hpp': No such file or directory

When I try compile jsmith's code on Visual C++ 2008, I get the above error...

What is #include <boost/lexical_cast.hpp>?

[elvenspike]

i believe boost is a custom library, one i don't have and clearly you don't either. for some reason that one i posted before didn't work with higher numbers. here's my fix :

#include <iostream>
using namespace std;

void FUNCT(int a, int b);

int main() {
	int a, b; // a is num to compare 1, b is num to compare 2
	a=1;
	b=2;
	FUNCT(a,b);
	a++;
	FUNCT(a,b);
	b++;
	FUNCT(a,b);
	a--;
	FUNCT(a,b);
	a++;
	a++;
	FUNCT(a,b);
	b--;
	FUNCT(a,b);
	b++;
	b++;
	a--;
	FUNCT(a,b);
	a++;
	FUNCT(a,b);
	return 0;
}

void FUNCT(int a, int b) {
	int c; // the output variable o.o
	int d; // the workz
	d = a+b;
	if (d == 7) {
		c = 1;
	} else {
		c = 0;
	}
	cout << "[ " << a << " + " << b << " = 7 ] is ";
	if ( c == 1 ) {
		cout << "true.\n";
	} else  if ( c == 0 ) {
		cout << "false.\n";
	} else {
		cout << "WTF : " << c << ".\n";
	}
}
		
		

[johnkravetzki]

VS doesn't provide boost library. You will have to download and install it

[jsmith]

elvenspike:

what happened to the simplicity?

Still, your solutions do not solve OP's problem. The knapsack problem asks

"given a set S of N integers, is there some subset of M integers within S that sum to K?"

Your solution only works for subsets M of size 2, and even then it is not generalized to
any subsets M.

[elvenspike]

oh im sorry, i misunderstood the question. I thought he was just asking for a set of X integers to be added and compared to Y values and given a true or false answer. which is what i did there.

[mamali]

thanks all.

[jLNv0pDG]

void Run( int target, [...] , int sum, const int* first, const int* last )
{

    for( ; first != last; ++first )
        if( sum + *first == target )
            [...]
        else if( sum + *first < target )
            Run( target, [...],  sum + *first, first + 1, last );
}

Phew. Ok, I've been staring at this piece of code for about the last 30 60 minutes trying to make sense of it and I think I finally have it. Correct me if I'm wrong here:

Run initiates a for loop with int* first = nums[0]. Then the else if function calls the Run function but it's not starting everything from scratch, it's a nested function which will make more sub-nested functions (term?) and then the original functions will resume once these sub-functions have done their thing.

The str stuff seems to generate the output in a similar way, with each bit of the string (wow, no variables in it at all!) being added as we go into more and more nested functions using + lexical_cast<string>( *first )....

Although, I don't get why const string& str is used in void Run( int target, const string& str, int sum, const int* first, const int* last ), instead of simply string str. I changed it and it still seems to work fine.

*is very impressed with that, even if I don't understand it all*

[jsmith]

const std::string& is used to avoid an extra copy of the string onto the stack.

I have an optimization "bug" in my original code. Either the std::sort() isn't necessary, or
to make the program run very slightly faster, there should be an "else break;" on the
if() inside Run().

Run is given as parameters:
target - the sum to look for
str - text string containing the numbers we've added so far
sum - the sum of the numbers we've added so far
first - the next number in the array to add
last - pointer one past the last number in the array

So given
target = 7
array = { 1, 2, 3, 4 };

The first call to Run is (pseudo-code)

Run( 7, "", 0, {1, 2, 3,4 } )

Run then adds 0 (sum) + 1 (first) == 1. 1 < 7, so it calls
Run( 7, "1", 1, { 2, 3, 4 } )

This invocation of Run adds 1 (sum) + 2 (first) == 3. 3 < 7, so it calls
Run( 7, "1 + 2", 3, { 3, 4 } )

This invocation of Run adds 3 (sum) + 3 (first) == 6. 6 < 7, so it calls
Run( 7, "1 + 2 + 3", 6, { 4 } )

This invocation of Run adds 6 (sum) + 4 (first) == 10. 10 > 7, so neither
the if nor the else execute. first is incremented by the for loop. first now
equals last (the array is empty), so this invocation returns back to the
previous one.

The previous invocation then increments its first (it pointed to 3, but now
it points to 4). It then adds 3 (sum) + 4 (first) == 7. 7 == 7, so it outputs
str ("1 + 2") + 4 = 7.

Etc.

One bug is that given the array { 1, 2, 3, 4, 4 }, it will output 1 + 2 + 4
twice and 3 + 4 twice, because it will find 4 twice. This can be solved
by adding a "return;" in the if() case of the loop.

[icerlion]

The worst method is calc all the subsum.Then you can find the subsum which is equal the k.
But it can be optimized.