Modifying "Coin change" program

**S0ULphIRE** · August 25th, 2011, 01:17 AM

Hey all, time for some dynamic programming! I've tried and failed, apparently I still don't understand the concept well enough to modify this the way I want.
Code I'm working with is from here: Java:: Coin Change Problem - dynamic programming - memoization - recursion

Basically I want the method to return not only the minimum number of coins needed (already works), but also the values of those coins. Sounds simple, but I'm stumped. Only thing I've changed is changing Hashtable to HashMap. Massive thanks to anyone who can help

public static HashMap<Integer, Integer> solved = new HashMap<Integer, Integer>();
 
 public static int kovanci(int[] k, int val) {
  // we've reached the end of recursion - a leaf
  // if the value is less than zero it means that the current combination is not solvable
  // if the value is zero, it means it is solvable
  if (val <= 0) return val;
 
  // for as many coins try to decrease the value for the coin value 
  // and try to solve the smaller problem
  int min = -1; //default: if it's not solvable
  for (int i = k.length - 1; i >= 0; i--) {
 
   // if the coin k[i] exists in the solution, it means the solution is
   // solutions(value - coin_value) + 1
   // eg. we have coins: 1, 3, 5 and the value is 11
   // if the coin 5 exists in the solution, try to solve the problem for value 11-5 = 6
   // the solution is smaller_solution + 1
   int newVal = val - k[i];
   int r;
 
   // dynamic programming - memoization
   // if we already have the minimum for the new value, fetch it (with time complexity O(1)), 
   // so that we don't recursively re-solve the problem and waste time
   if (solved.get(newVal) != null) {
    //solution = smaller_sollution + 1
    r = solved.get(newVal) + 1;
   } else {
    //try to solve the smaller problem
    r = kovanci(k, newVal);
    //if the solution is valid, the new solution is smaller_solution + 1
    if (r >= 0) r++;
    //else, keep the negative value - it means that it's not valid
    //eg: coins 3, 5, value 11 is not solvable, the solution is -1
   }
   // from all of the solutions, get the minimum value
   // and skip invalid solutions ( less than zero )
   if ((r > 0) && (min == -1 || r < min)) {
    min = r;
   }
  }
  // dynamic programming - memoization
  // once we do get the smallest possible solution, save it for later use
  // it saves A LOT of time and useless work, that's already been done
  solved.put(val, min);
  return min;
 }

**KevinWorkman** · August 25th, 2011, 07:28 AM

What do you mean you want it to return two things? That's not possible. And how does using a HashMap help you with this?

You can, however, return a List of things. I suggest you create a Coin Object that contains its value, and return a List of them.

**S0ULphIRE** · August 25th, 2011, 07:45 AM

I'll return it as an array, last entry will always be total number required, other elements will be coin values needed. HashMap just because Hashtable is old :p, tbh I haven't got the slightest grasp on HashAnything, just teaching myself Java still. Only been a month or so.

The bit I'm not sure on how to do is *how* to capture the coin value.

**KevinWorkman** · August 25th, 2011, 07:58 AM

Returning an array with mixed types seems really gross to me. Make an Object that holds that information instead.

Or go with my original suggestion- make a Coin Object that holds its own value- heck, that could just be an Integer. Then return a List of them- the number required is the size of the List.

**S0ULphIRE** · August 25th, 2011, 08:19 PM

Ok, so where would I implement the Coin Object? Lets simplify this, I'll just return coin values not number of coins required. How do I get those coin values and return them? I don't know at which point in the method I should be capturing the coin value or how I should be doing that.

What I want is this exact method, except instead of returning the number of coins needed, it returns the values of the coins needed.

**KevinWorkman** · August 26th, 2011, 08:40 AM

Originally Posted by S0ULphIRE

Ok, so where would I implement the Coin Object? Lets simplify this, I'll just return coin values not number of coins required. How do I get those coin values and return them? I don't know at which point in the method I should be capturing the coin value or how I should be doing that.

What I want is this exact method, except instead of returning the number of coins needed, it returns the values of the coins needed.

If you're not familiar with the code, then I suggest you go through it with a debugger and a fine-toothed comb until you understand exactly what it's doing. Copying and pasting code from the internet and then trying to add your own stuff to it is one surefire way to give yourself a headache.

Where do you determine which coin was just added to the total?

**S0ULphIRE** · August 27th, 2011, 01:24 AM

I'm teaching myself, and only started a little while ago. I've *heard* dynamic programming is pretty difficult, and from my experiences with doing exactly what you suggested I'd tend to agree. Sorry if I gave the impression that I know what I'm doing here :p

I've tried and failed, atm my Java knowledge just isn't good enough to jump right into dynamic programming. However, I'd still like the solution to this problem so I can implement it and make my life easier. Knowing the correct solution always helps in understanding the way something works too. I'd appreciate a solution more than I would a suggestion to 'try debugging code and just understand it'

Where do I determine which coin was just added to the total? No idea. Tried multiple spots, even tried adding a third argument to the parameters passed to the method, which was updated and passed back to the method every time this line was called

r = kovanci(k, newVal);

but no dice. Just ended up with array of lots of 0's and 1's :p
I'M STUCK. I'm running out of ways to say that lol

**KevinWorkman** · August 29th, 2011, 06:43 AM

Well, at some point you have to be removing a coin value from the total, right?

But really, if you got this code from somewhere else and you don't really understand what it's doing, I really suggest debugging and working through the code with a piece of paper and a pencil until you understand what every line is doing. Or better yet, start over- this is a pretty common algorithm, so it would be a good idea to write it yourself- how would you solve this problem by hand, without a program? It's going to be much easier to work with your own code than it is to work with copy-pasted code from the internet.

**S0ULphIRE** · August 29th, 2011, 07:30 PM

Thought about that. I believe the way this works is the Hashtable is filled with all the solutions under the desired amount, so at many points a value (not necessarily the right value) is being removed from the total? Then the most efficient value combination is chosen when the table is populated.
Problem is, as I said before, I don't know where to read it from or how or whether I need to pass another parameter that's read into the method each time or something else entirely.

How would you solve this problem by hand? Man good question. I don't even know how you would considering the only way to do it with a program is by trial and error pretty much (if my first sentence is correct anyway). Lol dude are you suggesting that I, a novice, rewrite a complex algorithm? Thanks for the vote of confidence but I have enough trouble with much simpler algorithms

I have one use for this code, selecting the most optimal set of values so I can quickly and easily select the right parts for a machine and not have to calculate a sub-optimal solution myself manually. If you can't or won't just simply show me how to do this, then please tell me. I do get what you're saying, that the best thing when coding is to understand and write it yourself. This is just way above my current level of expertise, but I still need the answers it'll provide me.

**KevinWorkman** · August 30th, 2011, 07:28 AM

Originally Posted by S0ULphIRE

How would you solve this problem by hand? Man good question. I don't even know how you would considering the only way to do it with a program is by trial and error pretty much (if my first sentence is correct anyway).

That's the problem, then. You absolutely have to know what you want the program to do before you can write it (or modify it). This is a fundamental aspect of programming, and it's one of the hardest- learning how to think through a problem and come up with a set of steps to solve it. Pretend you have a friend who has no idea how money works. Write down a set of basic instructions that he can follow to achieve your goal, and you'll have a basic algorithm that should be pretty easily translated into code.

Originally Posted by S0ULphIRE

Lol dude are you suggesting that I, a novice, rewrite a complex algorithm? Thanks for the vote of confidence but I have enough trouble with much simpler algorithms

I don't want to be a jerk, but the "coin return" program is one of the first programs many students write in their first programming course. I think it's less complicated than you think it is, and the code you're trying to use is doing a bunch of stuff that I don't think you need, which is just confusing you more. That's why I'm saying to start from scratch- plus it helps with that first bit about learning how to solve problems.

Originally Posted by S0ULphIRE

If you can't or won't just simply show me how to do this, then please tell me. I do get what you're saying, that the best thing when coding is to understand and write it yourself. This is just way above my current level of expertise, but I still need the answers it'll provide me.

Like I said, the coin return program is one of the first program students write. I honestly think it would be easier and better for you to start from scratch and write your own code than it will be for you to try to understand what somebody else is doing.

**S0ULphIRE** · August 31st, 2011, 01:22 AM

Haha apparently programming classes were much more hardcore back in the day, unless you're thinking of a Greedy algorithm? In which case yeah that's super easy, but that won't work for me, I have non-standard values.
i.e. for values 1,2,5,11 and sum 15, greedy algorithm would tell me optimal solution is 11,2,1,1 when it's clearly 5,5,5

**KevinWorkman** · August 31st, 2011, 07:08 AM

I guess I'm thinking of a greedy algorithm then. So you want the lowest number of coins? That's still not extremely difficult.

Anyway, you've heard my advice. Take it or leave it.

**S0ULphIRE** · August 31st, 2011, 08:11 AM

Yep lowest number of coins. If you reckon it's not extremely difficult, then help me and show me how you'd write it!

If not, then no worries.

**KevinWorkman** · August 31st, 2011, 08:17 AM

Originally Posted by S0ULphIRE

Yep lowest number of coins. If you reckon it's not extremely difficult, then help me and show me how you'd write it!

If not, then no worries.

Nice try.

Like I asked before- how would you do this on paper, without a computer? Pretend you have a really dumb friend that has no idea how to do it. Write out instructions that he could follow to accomplish your goal- when you have that, you'll have an algorithm that should be pretty easy to translate to code.

**Sean4u** · August 31st, 2011, 08:26 AM

greedy algorithm would tell me optimal solution is 11,2,1,1

Are you sure?

**S0ULphIRE** · August 31st, 2011, 08:28 AM

Yeah except if you think about what I said before it'll make sense now. The way it's solved is by calculating all values below the sum via trial and error and keeping the results. At the end, compare the results and choose optimal path. That's pretty hard to code though, or at least that's been my experience.

Why don't you want to write it? I'm not chasing the solution to this particular problem for fun lol, it'll be useful.

edit: @sean, 11+2+1+1=15 didn't ya know

**KevinWorkman** · August 31st, 2011, 08:35 AM

Originally Posted by S0ULphIRE

Yeah except if you think about what I said before it'll make sense now. The way it's solved is by calculating all values below the sum via trial and error and keeping the results. At the end, compare the results and choose optimal path. That's pretty hard to code though, or at least that's been my experience.

It's not hard to code. It might be hard to take somebody else's solution without understand what it's doing and try to hack away at it, but the theory is pretty standared. Hint: find all the different combinations that add up to your goal. Choose the shortest one.

Originally Posted by S0ULphIRE

Why don't you want to write it? I'm not chasing the solution to this particular problem for fun lol, it'll be useful.

We're not a code service. Doing your work for you isn't helping you. Stop asking, or I'm done trying to help.

Originally Posted by S0ULphIRE

edit: @sean, 11+2+1+1=15 didn't ya know

So is 11+2+2.

**S0ULphIRE** · August 31st, 2011, 08:48 AM

Might seem easy to you but it isn't to me.
You're right, doing my work for me wouldn't be helping. Because that wouldn't involve programming, as that's not my work. I figured I might get some java help on a java forum, so far you've given me advice on how to learn to program but that's it.

Have a read back through the thread, I've tried to stay nice with you after every snub. But apparently that's not good enough, meh hope you end up happier in life one day than you are now.

**KevinWorkman** · August 31st, 2011, 09:00 AM

I'm perfectly happy. But I'm not going to write your program for you. If you want somebody to do it for you, there's a Paid Java Projects forum here. That's not my style, as I'm here to learn how to educate people- and simply handing out code is not educational. If you aren't here to learn, you're in the wrong place.

**KevinWorkman** · August 31st, 2011, 09:03 AM

Originally Posted by S0ULphIRE

Might seem easy to you but it isn't to me.

And if you still want help, you'll have to be more specific than that- what about this don't you understand? Did you write out what you'd do like I suggested? Even somebody who doesn't want to learn how to program should understand what an algorithm is doing in order to use it...

If you want help, post an SSCCE demonstrating what YOU have tried (not code copy-pasted from the internet), and be specific about where you're stuck. And if you don't want help or to learn (keeping in mind that receiving some code you don't understand won't really help you at all), you're more than welcome to hire somebody on the Paid Java Projects forum.

**Sean4u** · August 31st, 2011, 09:04 AM

I've a feeling (can't be arsed to go through the hoops) that the problem of least-number-of-coins for arbitrary-sized coins will be related to stock-cutting and bin-packing. If you fancied searching for some potential solutions that are not just brute force, I'd say those would be good key-phrases. Then again, 'Coin change' is such a trivially-sized problem that it's hard to see why you'd spend time trying to improve on brute force when you're unlikely to use more than a few dozen operations each time and the time between uses of the code is colossal in computing terms (picking and handing someone human-scale objects isn't something that's ever going to occur at MHz).

It's not necessary to invent an 11p coin. Your simple biggest-first failure example works if you have to give 60 change when you only have denominations of 50, 20, 10, 5, 2, 1, but you're all out of 10s and 5s.

**S0ULphIRE** · August 31st, 2011, 06:49 PM

Yep, this is for cutting custom metal sheets on an old guillotine. There's a ton of different sizes and it goes down to some pretty small values. There's also more than one machine but only one set of spacers, hence the need for solutions which use the least possible number (to allow for both to be (more often than not) operated at the same time). Might have to end up just going with the GA after all.
0.011 is one of the spacer sizes, i was just looking at a list and pulled some random values from it. Then failed at adding up to 15 apparently

no sleep lol

@Kevin, That's all you needed to say! If I want help from you I gotta pay you. Got it.
I got stopped on the street by a pizza delivery guy wanting to know where a street was in the suburb I was in. I didn't know, so I pulled out my phone and searched it up for him and got him directions. Didn't charge him, mebbe I should've. After all, he didn't know how to do that. Maybe I should've told him to try just doing it himself or front up some money.
Sad world where you'll only help for money, *especially* when according to you the answer is so simple :/
I fix computers a ton, people bring 'em in all the time and yes I'll charge them. But if they bring in a USB stick and ask me why it's not working, and I *know* all it's gonna take is a simple format, then heck no I don't charge them. You and me are different like that I guess.

**KevinWorkman** · August 31st, 2011, 09:13 PM

Originally Posted by S0ULphIRE

@Kevin, That's all you needed to say! If I want help from you I gotta pay you. Got it.
I got stopped on the street by a pizza delivery guy wanting to know where a street was in the suburb I was in. I didn't know, so I pulled out my phone and searched it up for him and got him directions. Didn't charge him, mebbe I should've. After all, he didn't know how to do that. Maybe I should've told him to try just doing it himself or front up some money.
Sad world where you'll only help for money, *especially* when according to you the answer is so simple :/
I fix computers a ton, people bring 'em in all the time and yes I'll charge them. But if they bring in a USB stick and ask me why it's not working, and I *know* all it's gonna take is a simple format, then heck no I don't charge them. You and me are different like that I guess.

This is why I think you're a troll. You don't know me, and your arguments are illogical and pointless- and they make it less and less likely that anybody is going to want to help you. Had you actually read my post, you would know that I would NOT help you for money- that's not my thing.

I did give you several hints about how to do it (I actually gave you the basics of the algorithm, and I asked you several times to describe how you'd do it on paper- that's not even asking for code), but you want me to write the entire thing for you, which I'm not going to do. If you had shown the pizza delivery guy the directions and map and he had simply looked at you and said "I don't feel like driving there", would you have done his job for him?

If you had created the SSCCE or shown any effort whatsoever, I'd gladly help you (if I didn't enjoy helping people, I wouldn't spend my lunch breaks on this website). You want somebody to do your work for you- and even if it is pretty easy work (so is delivering a pizza), that's not going to happen.

You could have taken this time to create an SSCCE or write out a basic algorithm instead of trolling pointless arguments. But, you and me are different like that I guess.

**S0ULphIRE** · August 31st, 2011, 10:33 PM

I don't keep failed code blocks around to post up later, here's the last modification I'd tried.

    public static int dynTable(int[] shimArray, int cutSize, String temp){
        if (cutSize <=0) return cutSize;
        int min = -1; 
        for (int z =0; z <= shimArray.length-1; z++) 
        {  
            int updateAmount = cutSize - shimArray[z];
            int stampCount=0;
 
            if(!temp.equals("")){temp = temp +"," + Integer.toString(updateAmount);
            } else{ 
            temp = Integer.toString(updateAmount);
            }
 
            if (hash.get(updateAmount) != null) {
                stampCount = hash.get(updateAmount) + 1;
            } 
            else {
                stampCount = dynTable(shimArray, updateAmount, temp);
                valueList = temp;
                if (stampCount >= 0) stampCount++;
            }
            if ((stampCount > 0) && (min == -1 || stampCount < min)) {
                min = stampCount;
            }
        }
        hash.put(cutSize, min);
        return min;
    }

Complete rubbish? Thought so. Doesn't look like I have a darn clue what I'm doing? You'd be right there. Know why? This isn't my job, though you keep trying to say it is.

Me helping said pizza guy took 4 mins of my time (crap signal strength ftl) and after that he knew exactly what to do and was suitably grateful for me saving him a lot of time. I'm not asking you to write a program, fly over here, and do my job. I'm asking you to make a change to an existing program, one that I've tried and failed to do for a hell of a while now, then sit back and pat yourself on the back knowing you've made my day(s) much easier.

But no! I have to explain how I'd write it on paper, have to submit an SSCCE, have to have another go at writing out the algorithm. You're right, if I struggle with this long enough and read up enough stuff I'll eventually be able to cobble together my own program from scratch based off my own algorithm. Won't be fast, won't be as good as it can be, but hey I'll have done it myself!

You could have taken this time to *just simply help someone*. But, you and me are different like that I guess.

**KevinWorkman** · September 8th, 2011, 09:43 AM

Edit- This post was in response to Tjstretch offering a spoonfed solution that didn't actually solve the problem (he then claimed he was going to ignore complaints about spoonfeeding). This is one of my main gripes with spoonfeeding- most of the people who do it, don't read the entire thread, so what they post is usually misleading or flat out wrong. Even if a spoonfed answer is right (which is rare), it's still not helpful.

I'll keep this here for posterity:

Wow. You can ignore this all you want, but I highly recommend you read this: http://www.javaprogrammingforums.com...n-feeding.html

The reason I recommend this, is that's NOT what I meant (it was one solution I hinted at, but it's certainly not the best). It doesn't actually help with the algorithm, and it certainly doesn't answer the OP's core question. Why wouldn't you just use an Integer? Notice that I did suggest that, and notice that it's not what I was arguing can't be taught by spoonfeeding. I don't really see the point of your post.

Actually, I don't think I even consider that spoonfeeding, as it pretty much has nothing to do with the actual problem. It's a (small) piece of the problem, and I actually don't even think it's a good way to go. But it doesn't matter, because it doesn't actually have anything to do with the actual question!

And THAT, my friends, is the problem with spoonfeeders.

Thread: Modifying "Coin change" program

LinkBack

Thread Tools

Display

Modifying "Coin change" program

Related threads:

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Re: Modifying "Coin change" program

Similar Threads

"Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException" error

exception in thread "main" java.lang.nullpointerexception (Knights Tour program)

When I press on "new" in the menu in my GUI the program doesn't initialize (reset)

how to send a "spacebar" press to remote device via telnet using java program?

"java.lang.NoSuchMethodError: main" and "fatal exception occured."