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

现在的位置: 首页 > 综合 > 正文

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

2013年10月13日 ⁄ 综合 ⁄ 共 1603字 ⁄ 字号小中大 ⁄ 评论关闭

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