polynomial time algorithm for modified coin change

 

I thought of the following problem while thinking of coin change, but I don't know an efficient (pseudo-polynomial time) algorithm to solve it. I'd like to know if there is any pseudo-polynomial time solution or maybe some classic literature on it that I'm missing.

There is a well-known pseudo-polynomial time dynamic programming solution to the coin change problem, which asks the following:

You have coins, the of which has a value of . How many subsets of coins exist, such that the sum of the coin values is ?

The dynamic programming solution runs in , and is a classic. But I'm interested in the following slight generalization:

What if the coin no longer has just a value of , but instead can assume a set of values ? Now, the question is: How many subsets of coins exist, such there exists an assignment of coins to values such that the sum of the values of these coins is ?

(The classic coin change problem is actually an instance of this problem with for all , so I do not expect a polynomial time solution.)

For example, given and , and the following coins:

  • Then, there are subsets:

  • Take coin only, assign this coin to have value .
  • Take coin only, assign this coin to have value .
  • Take coins and , assign them to have values and , respectively or and , respectively—these are considered to be the same way.
  • Take coins , and , and assign them to have values , and , respectively.

    • The issue I'm having is precisely the third case; it would be easy to modify the classic dynamic programming solution for this problem, but it will count these two subsets as separate because different values are assigned, even though the coins taken are the same.

    So far, I have only been able to find the straightforward exponential time algorithm for this problem: consider each of the subsets, and run the standard dynamic programming coin change algorithm (which is ) to check whether this subset of coins is valid, giving an time algorithm. That's not what I'm looking for here; I'm trying to find a solution without the factor.

    Can you provide me with a pseudo-polynomial time algorithm to solve this question, or can it be proven that none exists unless, say, P = NP? That is, this problem is NP-complete (or similar).

    Maybe this is hard, but the way you asked the question it doesn't seem so.

    Take coins 1 and 3, assign them to have values 7 and 3, respectively or 6 and 4, respectively—these are considered to be the same way.

    Let us encode the two equivalent solutions in this way:

  • ((1, 3), (7, 3))
  • ((1, 3), (6, 4))

    • Now, when we memoize a solution, can't we just ask if the first element of the pair, (1, 3), has already been solved? Then we would suppress computing the (6, 4) solution.

    链接地址: http://www.djcxy.com/p/70678.html

    上一篇: 在有向图中检测周期的最佳算法

    下一篇: 用于修改硬币改变的多项式时间算法