最优找零2

coding>C++
940 词

题目描述

假设货币有$1,2,4,5,10$五种硬币，每种数量都无限多，现在给出金额$n$ $(1<=n<=1000000)$，求出最少的硬币数量

输入

现在给出金额$n$ $(1<=n<=1000000)$

输出

最少的硬币数量

样例输入

1
10

样例输出

1
1

题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[n+1];
    fill(a,a+n,0);
    int data[6] = { 0, 1, 2, 4, 5, 10 };
    for (int i = 1; i <= n; i++)
        a[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 5; j++)if (data[j] <= i)a[i] = min(a[i], a[i - data[j]] + 1);
    cout << a[n] << endl;
    return 0;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        int[] data = {0, 1, 2, 4, 5, 10};
        for (int i = 1; i <= n; i++)
            a[i] = i;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 5; j++)
                if (data[j] <= i)
                    a[i] = Collections.min(Arrays.asList(a[i], a[i - data[j]] + 1));
        System.out.println(a[n]);
    }
}