// ChangeBack.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//

#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
	//初始化 找零錢表
	//3 種零錢面額 
	int ** p = NULL;
	p = new int *[3];
	int d[3] = {1,3,5 };
	int i,j;
	int x;
	cin>>x;
	for (i = 0 ; i < 3;i++)
	{
		p[i] = new int[x+1];
	}
	for (i = 0 ; i <= x;i++)
	{
		p[0][i] = i;
	}
	
	int itemp1,itemp2;
	for (i = 1 ; i < 3; i++)
	{
		for (j = 0 ;  j < x+1;j++)
		{
			itemp1 = p[i-1][j];
			if (j -d[i] < 0)
			{
				itemp2 = 100000;
			}
			else
			itemp2 = p[i][j-d[i]] + 1;

			p[i][j] = itemp1<itemp2?itemp1:itemp2;
		}
	}

	//輸出初始化表
	for (i = 0; i < 3;i++)
	{
		cout<<endl;
		for (j = 0 ; j < x+1;j++)
		{
			cout<<p[i][j]<<" ";
		}
	}

	//開始查找最佳 零錢解決方案
	cout<<endl<<"the best solution to change"<<x<<"in to:"<<endl;
	i = 2;
	j = x;
    while(p[i][j] != 0)
	{
		if (p[i][j] != p[i-1][j] )//表名取了該面值的貨幣
		{
			cout<<"+"<<d[i];
			j -= d[i];
		}
		else
		{
			i--;
		}
	}

	cout<<endl;

	for (i = 0; i < 3 ;i++)
	{
		delete [] p[i];
	}
	delete []p;
	return 0;
}