Thread: Modifying "Coin change" program

Originally Posted by Tjstretch

If you didn't notice I deleted it.. I read the entire thread

Fair enough. But that's why people complain about spoonfeeding. Lesson learned, I suppose.

Originally Posted by Tjstretch

Yeah, hadn't thought about giving runnable code in quite that way, mostly because I wasn't agreeing on the premise that you don't learn from getting code to 'toy' with. Suppose I should thank you. However, you should add a tutorial on how to make pseudo-code or how to show code without "Spoon-Feeding."

That's a good idea.

But for the record, I do think that people learn from getting code to play around with- in fact, in my spare time I work on little open source programs that novice programmers can use as a start to their own cool, fun stuff (I'm not advertising myself, but for the curious, they are here). But I think there's a difference between providing a novice programmer with some code to jump start their ability to futz around, and doing a novice programmer's homework for him/her. That's spoon-feeding.

Man that's cool lol, not only do you not help, but any answer which contains the code I'm looking for you'll actually delete and vote to ban the user? Wow...
You seem to think this is homework. On the other forums I'm on (I'm not advertising myself, but for the curious, they are here and here, mainly first link. Do a search in the "programming" area for posts by S0ULphIRE) we have the same policies, i.e no posting solutions to homework problems. But I tell ya, this ain't homework! I program in a lot of other languages, learn java for funzies. But I'm all funned out on this one.
Check the programming areas, check my user profile (same name), check whatever. Should give you enough info/assurance that I'm not trolling
FYI ended up just using a greedy algorithm in c++, little GUI etc. Works fine, turns out I didn't need as much control as I thought would be necessary.
STILL though, I'd like to know how one would achieve this in Java

I didn't delete that post, and I actually said that I didn't count that post as spoonfeeding, since it simply showed you how to use an Object- which is an option I presented, but simply using Integers makes just as much sense.

But, I predict that you'd do it in Java exactly how you did it in c++.

Or, like I said back in August: Hint: find all the different combinations that add up to your goal. Choose the shortest one.

I would just use a dumb recursive tree-path-traverser. Take a List of Integers (those are your coin values). Choose one, add it to your total, add it to a List of "used coins" for that path, and recurse. When you reach the total, return the List. If you go over the total, return null (or whatever you want to return in case of failure). For any node in the tree, you'll return a List of Lists of Integers (one List for each coin choice you could make)- the shortest List is your solution.

Maybe I don't understand the problem correctly, but wouldn't a standard greedy algorithm (take the best available option, discard the rest) not always find the answer? For example, say you want to add up to 14 and you have 5, 5, 3, 2, and 2. A greedy algorithm would take the 5, then the other 5, then the 3 (because it gets closer to the goal of 14) but then it would be stuck. The way I described it, the algorithm would back up and try the 2 instead of the 3, eventually arriving at the correct answer.

Also, I'd like to point out that I hinted at my algorithm way back in August. Had you taken that hint and tried something, or even just pointed out what exactly you didn't understand about it, I would have been more than happy to explain it further, because I love stuff like this. Instead, you argued, asked for code, and criticized me every step of the way. That's fine, but it really doesn't make people want to help you. Maybe something to consider in the future.