本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答,若是满意,还请采纳,谢谢
- 问题分析
- 这是一个典型的凑零钱问题,可以使用动态规划来解决。动态规划的关键是定义状态和状态转移方程。
- 定义
dp[i][j]
表示前i
个硬币能否凑出金额j
。 - 状态转移方程为:
dp[i][j]=dp[i - 1][j] || dp[i - 1][j - coins[i]]
,其中coins[i]
是第i
个硬币的面值。 - 为了输出最小序列,我们可以从后往前推导选择了哪些硬币。
- 代码实现如下:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool isSmaller(int* arr1, int* arr2, int len) {
for (int i = 0; i < len; i++) {
if (arr1[i] < arr2[i]) {
return true;
} else if (arr1[i] > arr2[i]) {
return false;
}
}
return false;
}
void printCoins(int* coins, int* selected, int n) {
int flag = 0;
for (int i = 0; i < n; i++) {
if (selected[i]) {
if (flag) {
printf(" ");
}
printf("%d", coins[i]);
flag = 1;
}
}
printf("\n");
}
void coinChange(int* coins, int n, int m) {
bool** dp = (bool**)malloc((n + 1) * sizeof(bool*));
for (int i = 0; i <= n; i++) {
dp[i]=(bool*)malloc((m + 1) * sizeof(bool));
}
for (int i = 0; i <= n; i++) {
dp[i][0]=true;
}
for (int j = 1; j <= m; j++) {
dp[0][j]=false;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j < coins[i - 1]) {
dp[i][j]=dp[i - 1][j];
} else {
dp[i][j]=dp[i - 1][j] || dp[i - 1][j - coins[i - 1]];
}
}
}
if (!dp[n][m]) {
printf("No Solution\n");
return;
}
int* selected = (int*)malloc(n * sizeof(int));
int* minSelected = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
minSelected[i]=0;
}
int amount = m;
for (int i = n; i > 0; i--) {
if (dp[i - 1][amount]) {
selected[i - 1]=0;
} else {
selected[i - 1]=1;
amount -= coins[i - 1];
}
}
for (int i = 0; i < n; i++) {
minSelected[i]=selected[i];
}
for (int i = 1; i <= n; i++) {
int newAmount = m;
int* newSelected = (int*)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
newSelected[j]=0;
}
for (int j = n; j > 0; j--) {
if (dp[j - 1][newAmount]) {
newSelected[j - 1]=0;
} else {
newSelected[j - 1]=1;
newAmount -= coins[j - 1];
}
}
if (isSmaller(newSelected, minSelected, n)) {
for (int k = 0; k < n; k++) {
minSelected[k]=newSelected[k];
}
}
free(newSelected);
}
printCoins(coins, minSelected, n);
free(selected);
free(minSelected);
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int* coins = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
coinChange(coins, n, m);
free(coins);
return 0;
}
- 代码解释
- 在
isSmaller
函数中,比较两个数组的大小,按照题目中定义的序列大小关系进行比较。 printCoins
函数用于输出凑出金额的硬币组合。- 在
coinChange
函数中:- 首先动态分配二维数组
dp
,并初始化边界条件。 - 然后通过动态规划计算
dp
数组的值。 - 如果
dp[n][m]
为false
,表示无解,输出No Solution
。 - 否则,通过回溯找出一种硬币组合,再通过循环比较找出最小的硬币组合并输出。
- 在
main
函数中,读取输入的硬币个数n
、付款金额m
和硬币面值数组coins
,然后调用coinChange
函数解决问题,最后释放内存。