完整的题目描述在这里。

题目给了我们一些货物的价格a₁,...,a_m（不超过100000），要我们构造一种货币面值的方案x₁,...,x_n，使得所需要的纸币数量尽可能少。货币面值的方案必须满足

• x₁=1。
• 对于i<j，x_i一定是x_j的约数。

注意到不需要给出面值的方案，只是要求输出最少的张数，那么我们可以用动态规划解决。对于一个确定的方案，由于上述的性质，我们一定是用贪心的方法来付款。另外，价格不会超过100000，所以需要考虑的最大面值也是100000。对于一个面额x_i，付完款之后得到的余额是a₁%x_i,...,a_m%x_i。我们令f(i)表示用面值大于等于i的货币方案所付款所需要的纸币数量， 那么f(i)=min{f(j)+余额用i付款的张数 | i为j的约数}。具体的代码如下：

public class NewCoins {
  static final int MAXN = 100000;
  public int minCoins(int[] price) {
    int n = price.length;
    int[] f = new int[MAXN+1];
    for (int i = MAXN; i>0; i--) {
      for (int j = 0; j<n; j++)
        f[i] += price[j]/i;
      for (int j = 2*i; j<=MAXN; j += i) {
        int tmp = f[j];
        for (int k = 0; k<n; k++)
          tmp += (price[k]%j)/i;
        if (f[i]>tmp) f[i] = tmp;
      }
    }
    return f[1];
  }
}

至此，问题就解决了。

• Relative Posts