Backwards Scoring Fun

[achiah]

Hello everyone! I am currently making a scoring system project. It's not like the easy ones where you do something and get a point for that. It's the other way, in fact. The user makes up events that have different values for scores. Then, the user must input a number of FINAL scores. Instead of adding points to make a final score, this program takes final scores and tries to find the events that led up to it (in the most optimal way of course). Basically it's a backwards point system. Oh and some final scores are allowed to be impossible. For example, if the events had values of 2 and 5 and they chose a final score of 3, the program must recognize that.

I have the input part of the program done and it takes the user input as the project dictates it should. As for the calculation of what made up the final score, I'm at a loss for ideas. Maybe subtract the biggest event from the final score and keep doing that and using the next largest event to avoid negative numbers, until I reach 0? But then that would result in more "impossible" scores when really they are not. And if I were to try to continue from that happening, I'd start with the next biggest and go from there the same way? Would that work?

Basic input code structure:

#include <iostream>
using namespace std;

char storescheme(string scheme);
int storescore(int potscore);

int main() {
	for(;;)
	{
	int schemes, counter;
	cout << "Enter number of events: ";
	cin >> schemes;
	if(schemes==0)
	{
		break;
	}
	else
	{
	cout << "Enter the events to use: " << endl;
	for (counter=0;counter<schemes;counter++)
	{
		string scheme;
		if (counter==0)
		{
			cin.ignore();
		}
		getline(cin,scheme);
		storescheme(scheme);
	}
	for(;;)
	{
		int potscore;
		cin >> potscore;
		if(potscore==0)
		{
			break;
		}
		else
		{
			storescore(potscore);
		}
	}
	cout << endl;
	}
	}
	return 0;
}

char storescheme(string scheme)
{
	int counter1, counter2;
	string eventname;
	int eventscore[50];
	for(counter1=0;counter1<scheme.length();counter1++)
	{
		if (scheme[counter1]!=' ')
		{
			eventname[counter1]=scheme[counter1];
		}
		else
		{
			counter1++;
			break;
		}
	}
	for(counter2=0;counter1<scheme.length();counter1++,counter2++)
	{
		if (scheme[counter1]!=' ')
		{
		eventscore[counter2]=scheme[counter1];
		}
		else
		{
			break;
		}
	}
	cout << eventname;
	return 0;
}

int storescore(int potscore)
{
	return 0;
}

[achiah]

No ideas? C'mon guys I need some help here

[cire]

You could always go the brute force method and try all possible combinations of events if the numbers are small enough.

http://en.wikipedia.org/wiki/Bin_packing_problem

[achiah]

Considering the lack of ideas being brought forth, I might just do that. No other ways though? There's no telling how big those numbers can be, and something in the back of my mind is telling me I could go with the biggest event first and go to the next biggest as soon as the biggest might make it negative... and then if that does not work start with the next biggest instead from the beginning and so on?

[Manga]

but what if someone gave an event score of 1.

is it not possible that the final score be made only of these point 1 events?


EDIT.
okay I see. the number of events that took place is the logic clue.

[jidder]

id make an array of the scores.
Sort the scores in ascending order.
Then search for the first score below or equal to the the score your'e looking for.

Next find the score remaining after taking away the first score.
Search for the first score below or equal to that.

repeat.


e.g

create a counter
int scorecounter

Your scores
1,2,3,4,5,6,7,8,9,10

Final score
23


scorecounter = 23;
searches array
highest number below score counter is 10
so take 10 from score counter.
scorecounter = 13;
store event for 10;
Search array for highest number below scorecounter.
so take 9 from scorecounter.
store event for 9;
repeat
take 4 from score counter.
store event for 4;
scorecounter ==0;
finish loop

Edit.
p.s
You could also have an if statement to check whether or not the lowest score possible would take you past the final score and provide an error message in that case

Double Edit.
Just realised what you meant about "impossible" scores and that my answer is no help
sorry :(

[Rechard3]

maybe you're going for the Knapsack problem.

you can search Bruce Schneier's book for it:
Bruce Schneier - Applied Cryptography, Second Edition

i didn't try google, it might help you.

understanding this problem will most likely help you solve yours.

edit:
PS: i didn't read all the posts above.

[achiah]

Thanks for all the input guys! (lol input)
I'll see if I make some progress keeping these ideas in mind