Input a budget, output goods to buy so that the user will spend as much as possible

[Bubiche]

Hello and thank you for your time and patience to help me.
I'm struggling with this problem and I really don't know where to start, please help me with the algorithm, I mean the steps that my program need to do to solve this problem, I'm not asking for codes here.

Here is the problem: Given the user's budget and N kinds of table each has a quantity of 1 and follow the below structures

struct Tables {
char name[100];
int price;
};

Write a program to output the table(s) which the user need to buy to use up all of their money or having the least money left.
For example, if I have 4 tables A, B, C, D whose price is $400, $150, $900 and $200 respectively. When the user input their budget is $1000 then the program will return table C. When the user input $350 it will return tables B and D.

Please help me with the part how get the table(s) whose price or combined price is the the biggest and closest to the user's input budget?
At first I'm thinking about calculating the price of 1 table, combined of 2 tables, combined of 3 tables,... then compare their this differences with the budget but this method would be inefficient for a large amount of data.

Again, I'm only asking for the steps that my program need to do complete the task, I'll try to figure out the codes myself. Thank you very much for your help and sorry for my bad English, if the problem sounds unclear to you, please ask for information.

[SidPlay]

What do you mean by least money left as after that in the output you say that you can have both B and D ?

[Disch]

A relatively easy way to accomplish this would be with a simple recursive approach, where you step through the Tables and "fork" a path where you choose to buy or skip the next table in the list.

IE:

One path purchases Table[0]
One path doesn't purchase Table[0]

Then both paths fork off again at Table[1] (to create 4 paths)
then fork again at Table[2] (8 paths)
etc


Of course that gets unwieldly for large sets of data.

Writing this to be efficient on large sets of data gets pretty tricky. You'll have to figure out some way to determine "early outs" so you can spot when a path is less desirable than another path before having them run their full course.

One easy way to do this is to sort the Tables so that the least expensive ones are first. As soon as a path can't afford the next table in the list, it can stop running because it knows it won't be able to afford any more tables.


Though there's probably existing algorithms for this because this is a pretty common problem. I have no idea how to search for it though =x

[ne555]

0-1 knapsack problem where v_i = w_i
http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem

[Bubiche]

Thank you guys, you really made my day
Cheers

[Mathhead200]

This is an NP-Complete problem if I'm not mistaken. (There is no (known) polynomial time algorithm.) If you need to definitely always spend as much as possible, you can use brute force; like you said, try all the combinations possible. However, if you only need it to work well, but not perfect, try a greedy algorithm.

[Bubiche]

Thank you, doing it with brute force uses up too much memory do I don't think that would be the optimal solution. What's a NP-Complete problem? Sorry I've just started learning programming so I don't know much.
The solution for 0/1 knapsack problem seems to work for me but I can only get the maximum amount of money which I'll spend, can you please help me with a way to get which table(s) I need to buy to achieve that? I tried googling "find the elements in the knapsack" but still no result :<

[ne555]

> doing it with brute force uses up too much memory
¿memory? ¿why are you storing suboptimal solutions?
you only need to maintain the current best, so it would be O(n) in memory.

> a way to get which table(s) I need to buy to achieve that? I
The core of the algorithm m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
You simply need to know if the maximum was obtained with the inclusion of `v[i]'. So store that information in another table.

If the element was used, you test the next one in was_it_used[ i-1, maximum-v[i] ]
If the element was not used, you test the next one in was_it_used[ i-1, maximum ]


Note that there may be several combinations that yield the same result.


Edit:
> I tried googling "find the elements in the knapsack" but still no result :<
This was the first result http://stackoverflow.com/questions/7489398/how-to-find-which-elements-are-in-the-bag-using-knapsack-algorithm-and-not-onl using that exact query
(with duckduckgo because http://dontbubble.us/ )

[Mathhead200]

Brute force is most probably not optimal, and although you might be able to come up with a slightly faster algorithm, I doubt you need to trouble yourself, because if this problem is indeed NP-Complete then it probably won't be a whole lot faster. Plus, as ne555 said, if memory is becoming a problem, you are storing too much. Brute force here shouldn't use too much memory if done thoughtfully.

NP problems are, as I said, ones without a polynomial time algorithm; i.e. problems that have no particularly efficient solution as the input size gets big. (Okay NP is actually the set of polynomial and non-polynomial problems all put together.) NP-Complete just means it's equivalent to a bunch of other problems, and if you solve this one (with a polynomial time algorithm), you win a million dollars (no joke. An same if you prove it can't be done, but be warned, many computer scientist think it's impossible, mainly because there would be so many negative side-effects.)

Basically, some problems just don't have nice simple fast elegant solutions.