本文主要是介绍浙大PAT 1068题 1068. Find More Coins，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划，用dp[i][j]记录当使用前i个硬币时是否可以达到价值j，可以则为1，反之为0；用pre[i][j]记录当前第i个硬币是否在状态dp[i][j]中使用，是则为1，反之为0；
最后在寻找解时，如果pre[i][j]为1，则记录到ans（便于一起输出），反之则不断i--，则到pre[i][j]为1。
先对数据进行从大到小排序，保证最后的输出是smaller的，用下面的例子能更好的说明算法的思想。
input info
4 9
1 3 4 5
dp[i][j] info
0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 0 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1
pre[i][j] info
0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 1 0
1 0 0 1 1 1 0 1 1
result info
1 3 5
#include<stdio.h>
#include<stdlib.h>
int cmp(const void* ta,const void* tb){int* a=(int*)ta;int* b=(int*)tb;return *a<*b;
}
int dp[10001][101],pre[10001][101];
int arr[10001],ans[10001];
int main(){int i,j,n,m;scanf("%d %d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&arr[i]);}qsort(arr+1,n,sizeof(int),cmp);for(i=0;i<=n;i++){for(j=0;j<=m;j++){dp[i][j]=0;pre[i][j]=0;}}for(i=0;i<=n;i++){dp[i][0]=1;}for(i=1;i<=n;i++){for(j=arr[i];j<=m;j++){if(dp[i-1][j-arr[i]]){dp[i][j]=1;pre[i][j]=1;}else{dp[i][j]=dp[i-1][j];}}}if(!dp[n][m]){printf("No Solution\n");}else{int cnt=0;while(n>0){if(pre[n][m]){ans[cnt]=arr[n];m=m-arr[n];n=n-1;cnt++;}else{n--;}}for(i=0;i<cnt-1;i++){printf("%d ",ans[i]);}printf("%d\n",ans[cnt-1]);}return 0;
}这篇关于浙大PAT 1068题 1068. Find More Coins的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
