Talk:Change-making problem

Mathematical definition

I re-wrote the mathematical definition section. In particular I replaced the restriction that the number of coins of the j^th denomination, x_j, has to be 0 or 1 with the looser constraint that the number of coins of each type can be any non-negative integer. This is implicit in the (4,1,1) example given later in the article. With the tighter constraint there would be no solution at all for some values of W - for example, you can't make 9 from {1, 2, 5, 10...} if you can only use at most one coin of each denomination.

I found the same error in the List of knapsack problems article - the problem described there of minimising the number of items in the 0-1 knapsack problem is not the same as the change-making problem. Gandalf61 (talk) 13:32, 1 January 2009 (UTC)

Thank you Gandalf61 for your helpful contribution - appreciated! New Thought (talk) 20:54, 1 January 2009 (UTC)

There is a problem with the definition given in that it assumes that there is a coin of unit one(1). This is not the general definition of the Change-Making problem, but rather a restricted subset of it. The vast majority of the literature refers to the general problem and not this specific restriction. I would change the definition myself, but it is problematic in that the rest of the article's algorithms and citations will also have to be checked and possibly changed to match. RBarryYoung (talk) 14:45, 24 May 2019 (UTC)

Methods of Solving problems

There are also serious problems with this section. First and foremost there isn't even any representation of the canonical solution nor any of its predecessors (Martello, Toth (1990) "Knapsack Problems"). The Dynamic Programming solution is OK as presented but is not considered the best solution by far. Rather, it is a teaching example meant to demonstrate dynamic programming to students, it is not the canonical solution (nor even an acceptable one, in most cases). The Greedy method I think misrepresents a heuristic optimization of an approximate solution as though it were a deterministic solution of the general problem. No citations for this are given, so it is hard to confirm/deny this claim.

And finally, the "Dynamic programming with the probabilistic convolution tree" is very confused in that it appears to actually be a solution to a related but substantially different problem: the "Making Change" problem which seeks to find all possible solutions to making change to a specific total. Not surprisingly, many people not expert in this specific field confuse these two. The source cited is not an expert in this field, but in a closely related one of applied combinatorial programming. The article itself is NOT about the Change Making problem, but rather applying convolution trees to the problem of protein inference. In one section of the article it makes mention of other *possible* applications of their technique, including computing "the total number of unique ways to make change for a given amount of money". The authors thus recognize the difference between this possible application and the Change-Making problem, but whoever added this section did not. Further, the cited article only mentions it as a possibility. I have tried to search for this, but have not been able to find even a single instance of it ever actually being implemented. It could perhaps also be used to solve the Change Making problem as well, however, it's performance would be abysmal compared to the canonical solution. The performance analysis given appears to be a combination of original research, hand-waving and mistakes. No citation is given for this part.

RBarryYoung (talk) 15:21, 24 May 2019 (UTC)

The more I look at The Greedy Method section, the more problems I find. Even ignoring the problems mentioned above, this section does not actually present any solution method at all, not even an incorrect one, because the information presented is not an intelligible method. Rather it appears to be a collection of ruminations, specific to the single case presented, detailing how to back-justify the solution once it is already known. I cannot find any useful, accurate information at all in this section beyond the first sentence or two. Consequently I will delete most of this section and reword the remainder unless someone corrects or explains it better.

In fact, this whole article has so much incorrect information and is so lacking in other ways (history, etc.) that the entire thing should be completely rewritten. Unfortunately I do not have nearly enough time currently to do this myself.

(RBarryYoung) 2601:43:1:2879:D0AB:2641:44DE:4F26 (talk) 16:54, 29 May 2019 (UTC)

List of Problems with this Article

I have mentioned many of these in other sections here, but at this point the number of problem I am finding are so extensive that I am going to keep a list of them here until I or someone more qualified has the time to rewrite the article to fix them:

List of problems with the current article (misstatements, misleading, incorrect, etc.)

• Overview: "It is also the most common variation of the coin change problem..."

These are actually two different, though related, problems. Technically they are not variations of each other in the way that the 0-1 Change-Making problem is a variant of the canonical Change-Making problem. The Change-making problem *could* be described as a sub-problem of certain possible approaches to the Coin-change problem, but it is neither a subset of, nor a restriction of it. Also, no sources are given for this claim.

• Overview: "It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming.[1][2]"

First, as written this is an allusion to optimal complexity of the solution algorithm, which is incorrect as mere dynamic programming does not give optimal performance. The most optimal known solutions are Branch and Bound algorithms supplemented with dynamic programming (partial solution caches). Further, neither of the textbooks referenced make this claim and the writer appears to have misread their import. It may have been a miswritten attempt to say only that dynamic programming can produce a *correct* solution. However, if so then it needs to be rewritten, but it is then irrelevant wrt to the first part of the sentence and also out of place in the article.

• Mathematical definition: The definition given lacks citations but appears to be from one of the aforementioned student's textbooks. It is *not* the canonical/standard definition but a restricted variation of it where there is always a coin of value 1.

• Non-currency examples: Lacks citations.

• Methods of solving: The obvious, it fails to make any mention of Branch and bound solutions, the most successful class of algorithms for this problem for over 50-years.

• Methods of solving: Simple dynamic programming: This whole section is fine except that it presents it as the classical solution, instead of the simple example for teaching dynamic programming that it is.

• Methods of solving: Dynamic programming with the probabilistic convolution tree: As noted above, this is actually a solution to the Coin-change problem, not the Change-making problem. The sources cited actually confirm this (by description, not name).

• Methods of solving: Greedy method: As it is a heuristic in this problem space, it is not a solution to the Change-making problem and does not belong in this section. It is, however, important in the field both as a heuristic for optimal bounding estimates in Branch and Bound solutions, and also in the closely related problem of Canonical coin sets. Past the first sentence, it appears to be copied out-of-context (uncited) leading to it's incorrect claim which also lacks citations.

Hopefully I can get enough vacation time soon to work on all of this.

RBarryYoung (talk) 18:39, 13 June 2019 (UTC)

I think you are completely misreading the "It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming." claims, for one. (I haven't looked carefully at your other issues. It is completely true that the problem is weakly NP-hard. It is also completely true that dynamic programming finds its optimal solution in pseudo-polynomial time. There is no claim that dynamic programming is the only method of finding the optimal solution. The sentence is worded a little ambiguously, in that "optimally" could (but doesn't) mean "with optimal time complexity". So possibly it should be rewritten to say that dynamic programming finds the optimal solution. What is clearly being alluded to by this part of the article (but missing from your interpretation of it) is that "optimally" is used here as the opposite of "approximately". There are algorithms known for many related problems which can guarantee both polynomial time (rather than merely pseudo-polynomial) and any constant approximation ratio; in contrast, the dynamic program is merely pseudo-polynomial, but finds the optimal solution. Your proposed alternative of branch and bound is not in any sense more optimal: it can also find the optimal solution, but it does not find any better solution than straight dynamic programming. In contrast to dynamic programming it has zero guarantee on how much time it takes. And there is zero evidence that the time it takes is in any sense best possible. —David Eppstein (talk) 20:22, 13 June 2019 (UTC)