#include

#include

#include

#define MAX_change 200 //要找的零钱的总数

#define MAX_kind 30 //钱币面值的种类

#define MAX 9999

const char* INPUT_FILE = "change.txt";

const char* OUTPUT_FILE = "change_re.txt";

int u[MAX_kind][MAX_change];

int    coin[MAX_kind]; //钱币面值

int    b[MAX_kind][MAX_change]; //1:选择了coin[i-1] 2~∞:选择coin[i-1]的个数

int     real = 0; //实际找的零钱

FILE *in,*out;

void search_change(int n,int sum);

void print_change(int n,int sum);

void search_change(int n,int sum)

{

int i,j,k,small,num = 1,s;

for(j = 0; j <= sum ; j ++)

u[0][j] = MAX;

for(i = 1; i <= n; i ++)

for(j = 1;j <= sum ;j ++)

{

u[i][j] = u[i-1][j];

small = u[i-1][j];

for(k = 1 , s = coin[i-1] ; s <= j ; k ++ ,s += coin[i-1])

{

if(u[i][j-s] + k <= small) //注意这里的=号,否则结果就会出错!!!

{

small = u[i][j-s] + k; //注意:这里是u[i][j-s] ,不是 u[i-1][j]

num = k + 1;

}

}

u[i][j] = small;

b[i][j] = num;

num = 1;

}

real = sum;

for(i = sum; i >= 0 ; i --)

{

for(j = n; j > 0 ; j -- )

{

if(b[j][i] > 1)

return;

}

real--;

}

}

//打印结果

void print_change(int n,int sum)

{

if(n == 0 || sum < 0)

return;

if(b[n][sum] > 1)

{

print_change(n-1,sum - (b[n][sum]-1) * coin[n-1]);

//        printf("%d %d\n",n,sum-s[n-1]);

//        fputs(coin[n-1],out);

fprintf(out,"%d %d\n",coin[n-1],b[n][sum] - 1);

}

else

{

print_change(n-1,sum);

//        printf("%d %d\n",n,sum);

}

}

int main()

{

int i,j,num,sum;

if((in = fopen(INPUT_FILE,"r")) == NULL || (out = fopen(OUTPUT_FILE,"w")) == NULL)

{

printf("Can't open the file.");

getch();

return 1;

}

fscanf(in,"%d %d ",&num,&sum); //num:物品数量 sum:总共能装下的体积

for(i = 0;i < num ;i ++)

{

fscanf(in,"%d ",&coin[i]); //s[i]:第i个物品的体积,v[i]: 第i个物品的价值

}

search_change(num,sum);

fprintf(out,"实找金额为:%d\n",real);

print_change(num,real);

fclose(in);

fclose(out);

// getch();

return 0;

}