发布时间 : 星期一 文章算法设计与分析习题答案1-6章.更新完毕开始阅读
int main(int argc, char *argv[]) {
long m,n; cin>>m>>n;
cout< return 0; } 8. 考虑下面的货币兑付问题：在面值为(v1, v2, …, vn)的n种货币中，需要支付y值的货币，应如何支付才能使货币支付的张数最少，即满足 nn?xvi?1ii?y，且使?xi最小（xi是 i?1非负整数）。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。 #include int a[N][M]; int value[M]; using namespace std; int main() { while(true) { int i,j,k; int x,y,z; cout<<\输入货币种类的个数：\ cin>>x; cout<<\从小到大输入货币的价值，其中第一个必须为一：\ for(i=1;i<=x;i++)//x为货币种类的个数 { cout<<\ cin>>y; value[i]=y; } cout<<\输入要兑换的钱的价值：\ cin>>z;//z为钱 for(j=0;j<=z;j++) a[j][0]=0; for(k=0;k<=x;k++) a[0][k]=0; for(i=1;i<=z;i++) { for(j=1;j<=x;j++) { if(value[j]==i) a[i][j]=1; else if(value[j]>i) a[i][j]=a[i][j-1]; else a[i][j]=a[i-value[j]][j]+1;//相当于把乘法换成加法，即碰到一个钱数于 兑换货币自身价值时，返回到 钱数减去该货币值的地方，其值再加1// }//for } cout<<\兑换的最小货币个数是：\ }//while return 0; }