【输入形式】 第一行一个整数n( n ≤ 1000 ),表示硬币个数。 第二行n个整数。 【输出形式】 所选硬币最大金额。使用c语言
时间: 2024-02-17 19:02:32 浏览: 24
这是一个经典的动态规划问题,以下是一种解法,时间复杂度为O(n)。
```c
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n;
scanf("%d", &n);
int *coins = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
int *dp = (int *)malloc(sizeof(int) * n);
dp[0] = coins[0];
for (int i = 1; i < n; i++) {
dp[i] = max(coins[i], coins[i] + dp[i - 1]);
}
printf("%d\n", dp[n - 1]);
free(dp);
free(coins);
return 0;
}
```
输入示例:
```
6
7 3 8 4 2 9
```
输出示例:
```
23
```
相关问题
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]即为所需的最少硬币数。
以下是示例代码:
```c
#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。 【输出形式】 找零所需的数量最少的硬币数目。
这是一个经典的动态规划问题,可以使用贪心算法求解。
首先,将硬币面值从大到小排序,然后从大到小依次尝试用面值最大的硬币去找零。如果当前硬币面值大于等于剩余需要找零的金额,则将该硬币个数加上剩余需要找零的金额除以当前硬币面值的商,即可得到所需硬币的最小数量。
代码如下:
```python
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数组。
代码如下:
```python
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])
```