【输入形式】 第一行一个整数n（ n ≤ 1000 ），表示硬币个数。 第二行n个整数。 【输出形式】 所选硬币最大金额。使用c语言

以下是一个简单的贪心算法实现，时间复杂度为O(nlogn)。

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

int main() {
    int n;
    scanf("%d", &n);
    int* coins = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &coins[i]);
    }
    qsort(coins, n, sizeof(int), cmp);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (sum < coins[i]) {
            sum += coins[i];
        }
    }
    printf("%d\n", sum);
    free(coins);
    return 0;
}

首先将硬币按面值从大到小排序，然后从大到小依次考虑是否选择当前硬币，如果当前硬币的面值大于当前总金额，则选择当前硬币，否则直接跳过。最终的总金额即为所选硬币的最大金额。

相关问题

c语言解决第一行一个整数n（ n ≤ 10000 ），表示需找零的金额。 第二行一个整数m（ m ≤ 100 ），表示硬币面值的个数。 第三行为m个整数，表示m个硬币的面值d1<d2<…<dm，其中d1=1。

好的，这个问题可以使用动态规划来解决。我们可以定义一个数组dp，其中dp[i]表示找零i元所需要的最少硬币数。则有以下状态转移方程：

dp[i] = min(dp[i], dp[i - coins[j]] + 1)，其中coins[j]表示第j个硬币的面值。

首先将dp数组初始化为无穷大，然后将dp[0]赋值为0。接着，我们遍历硬币面值数组，对于每个硬币面值，再从1到n遍历一遍，更新dp数组。最终，dp[n]即为所需的最少硬币数。

以下是示例代码：

#include <stdio.h>
#include <limits.h>

#define MAXN 10010
#define MAXM 110

int dp[MAXN]; // dp数组
int coins[MAXM]; // 硬币面值数组

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    // 初始化dp数组
    for (int i = 1; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;

    // 读入硬币面值数组
    for (int i = 1; i <= m; i++) {
        scanf("%d", &coins[i]);
    }

    // 动态规划
    for (int i = 1; i <= m; i++) {
        for (int j = coins[i]; j <= n; j++) {
            dp[j] = dp[j] < dp[j - coins[i]] + 1 ? dp[j] : dp[j - coins[i]] + 1;
        }
    }

    // 输出结果
    printf("%d\n", dp[n]);

    return 0;
}

第一行一个整数n（ n ≤ 10000 ），表示需找零的金额。 第二行一个整数m（ m ≤ 100 ），表示硬币面值的个数。 第三行为m个整数，表示m个硬币的面值d1<d2<…<dm，其中d1=1。 【输出形式】 找零所需的数量最少的硬币数目。

这是一个经典的动态规划问题，可以使用贪心算法求解。

首先，将硬币面值从大到小排序，然后从大到小依次尝试用面值最大的硬币去找零。如果当前硬币面值大于等于剩余需要找零的金额，则将该硬币个数加上剩余需要找零的金额除以当前硬币面值的商，即可得到所需硬币的最小数量。

代码如下：

n = int(input())  # 需找零的金额
m = int(input())  # 硬币面值的个数
coins = list(map(int, input().split()))  # 硬币面值

count = 0  # 硬币数量
for i in range(m-1, -1, -1):
    if coins[i] <= n:
        count += n // coins[i]
        n %= coins[i]
    if n == 0:
        break

print(count)

如果硬币面值不是特殊的，比如面值为1、2、5、10、20、50、100，那么就需要使用动态规划求解。具体做法是定义一个长度为n+1的数组dp，其中dp[i]表示找零i元所需的最少硬币数目。初始化dp[0]=0，其余元素均为正无穷大。然后依次枚举硬币面值，对于每个面值，再枚举需要找零的金额，更新dp数组。

代码如下：

n = int(input())  # 需找零的金额
m = int(input())  # 硬币面值的个数
coins = list(map(int, input().split()))  # 硬币面值

dp = [float('inf')] * (n+1)
dp[0] = 0

for i in range(m):
    for j in range(coins[i], n+1):
        dp[j] = min(dp[j], dp[j-coins[i]] + 1)

print(dp[n])