算法设计与分析习题答案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 #define N 100000 #define M 20

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; }