changeback.cpp

C++动态规划的算法例子

// ChangeBack.cpp : 定义控制台应用程序的入口点。
//

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