贪心算法实例c语言

㈠ C语言关于贪心算法的（很简单）

LZ在开始研究ACM嘛？
#include
int
least_num_cash(int
_money)
{
/*直接贪心，能用大张的钞票尽量用大张的*/
int
ret=0;
while(_money!=0)
{
if(_money>=100)
{
_money-=100;
}
else
if(_money>=50)
{
_money-=50;
}
else
if(_money>=20)
{
_money-=20;
}
else
if(_money>=10)
{
_money-=10;
}
else
if(_money>=5)
{
_money-=5;
}
else
if(_money>=2)
{
_money-=2;
}
else
if(_money>=1)
{
_money-=1;
}
ret++;
}
return
ret;
}
int
main()
{
int
n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("%d\n",least_num_cash(m-n));
}
return
0;
}

㈡ C语言贪心算法 背包问题

if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交换操作的三步要用{}括起来,不然只有t=T[i];是if的执行语句

㈢ 收集各类贪心算法（C语言编程）经典题目

举个例子,假如你买东西，老板需要找给你99分钱，他有上面面值分别为25分，10分，5分，1分的硬币（都是假如，不符合实际），他得找你3个25分，2个10分的，4个1分的才为最佳方案！
用贪心算法编写程序实现！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}

㈣ C语言 贪心算法求背包问题

是你的冒泡排序出了问题~

你吧 原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了
所以 你输出的时候是按 1-2-3输出的话 就等于第一个是原来的X2 第二个是X1第三个是X3
而且你的冒泡排序用错了 只比较了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去学校帮你重新改改 我家的机器没有C++
周一晚上我会上传答案~我最近正好也要做算法的作业~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体，再考虑小的物体*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入数量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

㈤ C语言，贪心算法，货币找零问题

贪心算法找零就是现实中从最大面额开始找的思路。不代表是最优解，只是算法之一。

由于面额输入顺序不定，我先对输入的面额进行降序排序。

下面代码：

#include <stdio.h>

#include <malloc.h>

int main()

{

int i,j,m,n,*ns=NULL,*cn=NULL,sum=0;

printf("请输入总金额m及零钱种类n："),scanf("%d",&m),scanf("%d",&n);

printf("请分别输入%d种零钱的面额： ",n);

if(!(ns=(int *)malloc(sizeof(int)*n))) return 1;

if(!(cn=(int *)malloc(sizeof(int)*n))) return 1;

for(i=0;i<n;i++) scanf("%d",&ns[i]);

//------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除）

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i];

//-------------------------------------------------------------------

for(i=0;i<n;i++)//贪心算法，从最大面额开始

if(m>=ns[i])

cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d张 ",ns[i],cn[i]);

printf(" 最少使用零钱%d张 ",sum);

return 0;

}

㈥ 贪心算法求最优分解 C语言程序

思路：对于一个整数n，无论分成多少个数的和，都是这些数相同或相差最少的时候，它们的积才最大。如，对于数 4, 2 * 2最大；对于9，分成三个数3 * 3 * 3最大，分成两个数4 * 5最大。。。数学里可以证明。
然后分治法就行了
1,2,3这三个数不可分，本身最大，遇到它们直接返回就行了，其它数分完递归调用。

㈦ 很简单的C语言贪心算法，用map做的，但我对map有个问题

改成 pw.insert(make_pair(5,10));