实验要求
采用动态规划思想实现：
设计原理
算法伪代码
核心代码
void Coin(){
int i, j;
for (i = 1; i <= y; i++) //i=1时
{
m[1][i] = i * coin[1].weight;
s[1][i] = 1;
}
for (i = 2; i <= n; i++)
{
for (j = 1; j <= y; j++)
{
if (coin[i].value <= j)
{
if (m[i - 1][j] > (m[i - 1][j - coin[i].value] + coin[i].weight))
{
m[i][j] = m[i - 1][j - coin[i].value] + coin[i].weight;
s[i][j] = i;
}
else
{
m[i][j] = m[i - 1][j];
s[i][j] = s[i-1][j];
}
}
else
{
m[i][j] = m[i - 1][j];
s[i][j] = s[i - 1][j];
}
}
}
}
实验结果
算法时间复杂度分析
实验总结
