硬币变化的变化

Question

因此，典型的硬币兑换问题会要求您确定您是否可以使用面值为x1，x2，...，xn的无限制硬币对值v进行更改，但我想知道如何使用AT MOST中的每枚硬币解决相同的问题？

对于原来的问题，我知道你可以遍历值的前缀并查看你是否可以对v-x_i进行修改，但是当它被限制在每个面额最多一个硬币时，我就不知所措了。

任何提示，让我开始？我也许认为你也可以迭代教派的前缀。不知道虽然...

Answer 1

对于硬币的变化问题，你可以使用向前或向后的复发。在你的声明中，你反悔了。这里我会给出一个前向方法，它可以轻松解决无限版本和AT-MOST-ONCE版本

假设f是一维布尔数组。 f [i]意味着你是否可以为价值i做出改变。最初，f [0] =真，其他人等于假。

无限版：

for (int i=1;i<=n;i++) 
    for (int j=0;j<v;j++) 
     if (f[j]) 
      f[j+x[i]]=true; 

AT-最多一次版本：

for (int i=1;i<=n;i++) 
    for (int j=v-1;j>=0;j--) 
     if (f[j]) 
      f[j+x[i]]=true; 

，唯一的区别是环j中的顺序。

一个例子，这有助于理解ü：

假设仅存在一种硬币的花费2.即X [1] = 2。并且在第一个算法之后，u可以得到f [0] = f [2] = f [4] = f [6] = f [8] = f [10] =真。

但是对于第二种算法，u只能得到f [0] = f [2] = true。