算法设计与分析实验五-动态规划

【问题1】给定面值分别为{v1,v2,…,vn}的n种硬币, 用这些硬币来支付价值为y的金额,要求寻找一种硬币个数最少的支付方案。例如,给定v1=1、v2=5、v3=6、v4=11,y=29,使用4种货币支付29的货币,最少硬币数为4,方案是:11+11+6+1。

#include <iostream>
#include <vector>

using namespace std;

const int INF = 9999;

vector<int> vCoins;
vector<int> vCoinNumbers;
vector<int> vPath;

void PutChanges(int money, int n)
{
	for (int i = 1; i <=money ; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i-vCoins[j]>=0)
			{
				int num = vCoinNumbers[i - vCoins[j]] + 1;
				if (num<vCoinNumbers[i])
				{
					vCoinNumbers[i] = num;
					vPath[i]=i-vCoins[j];
				}
			}
		}
	}
}
void DisplayResult(int money)
{
	if (money>vPath[money])
	{
		DisplayResult(vPath[money]);
		cout << money - vPath[money] << " ";

	}
}
int main()
{
	int n;
	
	cin >> n;
	
	for (int  j = 0; j < n; j++)
	{
		int x;
		cin >> x;
		vCoins.push_back(x);
	}

	int money;
	cin >> money;
	vCoinNumbers.push_back(0);
	for (int i = 0; i <= money; i++)
	{
		vCoinNumbers.push_back(INF);
		vPath.push_back(0);
	}
	PutChanges(money, n);
	cout << vCoinNumbers[money] << endl;
	DisplayResult(money);
}

【问题2】给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。编写一个程序求所有路径中最小的路径和以及对应的这条路径。```cpp

#include <iostream>
#include <vector>

using namespace std;

typedef struct tagPoint
{
	int m;
	int n;
}Point;

vector<vector<int>> vArray;
vector<vector<int>> vDistance;
vector<vector<Point>> vPath;

void ShortestDistance(int m, int n)
{
	for (int j = 0; j < n; j++)
	{
		if (j==0)
		{
			vDistance[0][j] = vArray[0][j];
			vPath[0][j] = { 0,j };
		}
		else
		{
			vDistance[0][j] = vDistance[0][j - 1] + vArray[0][j];
			vPath[0][j] = { 0,j - 1 };
		}
	}

	for (int i = 0; i < m; i++)
	{
		if (i==0)
		{
			vDistance[i][0] = vArray[i][0];
			vPath[i][0] = { i,0 };
		}
		else
		{
			vDistance[i][0] = vDistance[i - 1][0] + vArray[i][0];
			vPath[i][0] = { i - 1,0 };
		}
	}

	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (vDistance[i-1][j]<vDistance[i][j-1])
			{
				vDistance[i][j] = vDistance[i - 1][j] + vArray[i][j];
				vPath[i][j] = { i - 1,j };
			}
			else
			{
				vDistance[i][j] = vDistance[i][j - 1] + vArray[i][j];
				vPath[i][j] = { i,j - 1 };
			}
		}
	}
}

void DisplsyPath(int m, int n)
{
	if (m==0&&n==0)
	{
		cout << "(" << m << "," << n << ")";
		return;
	}

	DisplsyPath(vPath[m][n].m, vPath[m][n].n);
	cout << "->" << "(" << m << "," << n << ")";
}

int main()
{
	cout << "dd";
	int m, n;

	cin >> m >> n;

	vector<int> vZero;
	vector<Point> vPoint;

	for (int k = 0; k < n; k++)
	{
		vZero.push_back(0);
		vPoint.push_back({ -1,-1 });
	}

	for (int i = 0; i < m; i++)
	{
		vector<int> vLine;
		for (int j = 0; j < n; j++)
		{
			int x;
			cin >> x;
			vLine.push_back(x);
		}

		vArray.push_back(vLine);
		vDistance.push_back(vZero);
		vPath.push_back(vPoint);
	}

	ShortestDistance(m, n);
	DisplsyPath(m - 1, n - 1);
	cout << endl << vDistance[m - 1][n - 1] << endl;
}
上一篇 下一篇
内容结束