2619: 动态规划-硬币问题
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：2
提交：2
正确率：100.00% 命题人：
题目描述
已知有 $n$（$1 \le n \le10$）种不同面值的硬币，各种硬币面值存于数组 $T$[$1:n$]，各种面值的个数存在数组 $NUM$[$1:n$]中，需要找零的钱数为 $m$（$0 \le m \le 100$）。设计一个算法，计算找钱 $m$ 的最少硬币数以及不同硬币面值的个数（使用动态规划）。
要求：
第 $1$ 行输入 $1$ 个整数，表示不同面值的硬币数 $n$。
第 $2$ 行输入 $2$ 个整数，分别表示第 $2$ 个硬币的面值和个数。
第 $3$ 行输入 $2$ 个整数，分别表示第 $3$ 个硬币的面值和个数。
...
第 $n+1$ 行输入 $2$ 整数，分别表示第 $n$个硬币的面值和个数。
第 $n+2$ 行输入 $1$ 整数，表示钱数 $m$。
第 $n+3$ 行输出 $1$ 整数，表示计算出来的最少硬币数量。
最后 $1$ 行直接输出每种硬币的个数（相邻两个数据之间用 $1$ 个空格隔开）。
要求：
第 $1$ 行输入 $1$ 个整数，表示不同面值的硬币数 $n$。
第 $2$ 行输入 $2$ 个整数，分别表示第 $2$ 个硬币的面值和个数。
第 $3$ 行输入 $2$ 个整数，分别表示第 $3$ 个硬币的面值和个数。
...
第 $n+1$ 行输入 $2$ 整数，分别表示第 $n$个硬币的面值和个数。
第 $n+2$ 行输入 $1$ 整数，表示钱数 $m$。
第 $n+3$ 行输出 $1$ 整数，表示计算出来的最少硬币数量。
最后 $1$ 行直接输出每种硬币的个数（相邻两个数据之间用 $1$ 个空格隔开）。
测试代码 复制
#include <stdio.h>
#define MAXINT 1000000 //假设MAXINT表示内存中能够存储的最大整数
int T[11], NUM[11], X[11]; //T[i]:第i种硬币面值，NUM[i]:第i种硬币个数，X[i]表示取得最优值时第i种硬币的个数
int c[11][101]; // 需要填写的二维表格
int coin(int n,int m) {
for(int j=0; j<=m; j++) { //填写表格中第n行数据
if (j%T[n]==0 && j/T[n]<=NUM[n]) c[n][j]=j/T[n];
else c[n][j]=MAXINT;
}
for(int i=n-1; i>=1; i--){
for(int j=0; j<=m; j++){
}
}
return c[1][m];
}
void printOptimalSolution(int n, int j) {
for(int i=1; i<=n; i++) {
if (c[i][j]==c[i+1][j]) X[i]=0;
else {
}
}
}
int main(void) {
int i,n,m,result;
scanf("%d", &n);
for(i=1; i<=n; i++) {
scanf("%d", &T[i]);
scanf("%d", &NUM[i]);
}
scanf("%d",&m);
result=coin(n,m);
printf("%d\n", result);
printOptimalSolution(n,m);
for(i=1; i<=n; i++) printf("%d ",X[i]);
return 0;
}输入样例 复制
4
1 3
2 4
5 2
10 2
17输出样例 复制
3
0 1 1 1提示
本题需要输出最优解，最优值唯一但是最优解不一定唯一，本题假设优先选用编号较小的硬币。