动态规划——找零钱问题 收藏

view plaincopy to clipboardprint?
#include <iostream>
using namespace std;
const int M=1000;
const int N = 3;
int coint[N];
int count[M+1];//count[i]表示凑合数量为i所需最少的钱币数量,则count[i]=min{count[i-coint[j]]+1},其中0<=j<=N-1
int trace[M+1];//每个表示count[i]在取最小值时的选择，即上式中的j
int dp_count(int m)
{
int i = 0;
int j = 0;
for(i=0;i<M+1;i++)
count[i]=0xffff;
count[0] = 0;
for(i=0;i<=m;i++)
{
for(j=0;j<N;j++)
if(coint[j]<= i && count[i-coint[j]]+1 < count[i])
{
count[i] = count[i-coint[j]]+1;
trace[i] = coint[j];
}
}
return count[m];
}
void print(int m)
{
if(m==0)
return;
else
{
cout << trace[m] << " ";
print(m-trace[m]);
}
}
int main()
{
int i=0;
for(i=0;i<N;i++)
cin>>coint[i];
int m;
cin >> m;
cout<<dp_count(m)<<endl;
print(m);
}
#include <iostream>
using namespace std;
const int M=1000;
const int N = 3;
int coint[N];
int count[M+1];//count[i]表示凑合数量为i所需最少的钱币数量,则count[i]=min{count[i-coint[j]]+1},其中0<=j<=N-1
int trace[M+1];//每个表示count[i]在取最小值时的选择，即上式中的j
int dp_count(int m)
{
int i = 0;
int j = 0;
for(i=0;i<M+1;i++)
count[i]=0xffff;
count[0] = 0;
for(i=0;i<=m;i++)
{
for(j=0;j<N;j++)
if(coint[j]<= i && count[i-coint[j]]+1 < count[i])
{
count[i] = count[i-coint[j]]+1;
trace[i] = coint[j];
}
}
return count[m];
}
void print(int m)
{
if(m==0)
return;
else
{
cout << trace[m] << " ";
print(m-trace[m]);
}
}
int main()
{
int i=0;
for(i=0;i<N;i++)
cin>>coint[i];
int m;
cin >> m;
cout<<dp_count(m)<<endl;
print(m);
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/08/21/4471476.aspx