A. 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;
}
B. 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. c语言问题急！！！（用贪心算法）
题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
Code:
//找零钱算法//By falcon//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案 public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;i<k;i++) { num<i>=n/m<i>; n=n%m<i>; } return num; }
[Ctrl+A Select All]
演示代码
Code:
public class zhaoqian{ public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length]; num=zhaoqian(m,n); System.out.println(n+"的找钱方案："); for(int i=0;i<m.length;i++) System.out.println(num<i>+"枚"+m<i>+"面值"); } public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;i<k;i++) { num<i>=n/m<i>; n=n%m<i>; } return num; }}
[Ctrl+A Select All]
演示结果：
falcon@falcon:~/program/java$ javac zhaoqian.java
falcon@falcon:~/program/java$ java zhaoqian
99的找钱方案：
3枚25面值
2枚10面值
0枚5面值
4枚1面值
D. C语言贪心算法 背包问题
if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交换操作的三步要用{}括起来,不然只有t=T[i];是if的执行语句
E. 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;
}
F. 求C语言或c++的贪心算法的例题
比如：
int
a=3,b=4,c;
c=a+++b;
将被解释为
c=(a++)+b;
而不会被解释为
c=a+(++b);
贪心算法的主要意义是从左至右依次解释最多的符号！
G. 贪心算法求最优分解 C语言程序
思路：对于一个整数n，无论分成多少个数的和，都是这些数相同或相差最少的时候，它们的积才最大。如，对于数 4, 2 * 2最大；对于9，分成三个数3 * 3 * 3最大，分成两个数4 * 5最大。。。数学里可以证明。
然后分治法就行了
1,2,3这三个数不可分，本身最大，遇到它们直接返回就行了，其它数分完递归调用。
H. 求找零钱问题和背包贪心算法问题（背包里物体可分解）C语言程序
分数太少了，第一个是动态规划，第二个是贪心，都挺简单的
还是给你写吧
第一题：
#include<stdio.h>
#include<memory.h>
int a[2000],b[200000],n,m,i,j;
int main()
{
scanf("%d",&n);//钱币种类
for (i=0;i<n;i++)
scanf("%d",&a[i]);//每个钱币的面值
scanf("%d",&m);//需要计算的钱币的面值
memset(b,0,sizeof(b));
for (i=0;i<n;i++)
b[a[i]]=1;
for (i=1;i<=m;i++)
for (j=0;j<n;j++)
if (i-a[j]>0)
if (b[i]==0)
{
if (b[i-a[j]]!=0)
b[i]=b[i-a[j]]+1;
}
else
{
if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i])
b[i]=b[i-a[j]]+1;
}
if (b[m]==0) printf("-1\n");//找不开输出-1
else printf("%d\n",b[m]);//可以找到交换策略，输出最小票数
return 0;
}
第二题：
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}
I. 收集各类贪心算法（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();
}
J. 关于一道C语言的背包问题，用的是贪心算法
#include "iostream.h"
#include "stdio.h"
#include <cstdlib>
struct stone
{
int name;
int weight;//物品的剩余重量
int weight_t;//物品的重量
float benefit;//物品的价值
//float b;
};
//按物品的效益排序
void sort(stone *data,int num)
{
//仅剩一个元素时排序完毕
if(num<1)
return;
int low=0,high=num;
stone key_s=data[low];//取数组的第一个作为关键字
float key=(float)key_s.benefit/key_s.weight;
int empty=low;//目标位置初始位置为low指向的位置
while(low<high)
{
if(low==empty)//后面的指针向前走
{
//找到比关键字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--;
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high];
empty=high;
}
}
else if(high==empty)//前面的指针向后走
{
//找到比关键字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++;
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low];
empty=low;
}
}
}
data[empty]=key_s;//把关键字放到划分完毕后两部分的中间位置
//关键字前面的数列继续递推
if(empty>1)
sort(data,empty-1);
//关键字后面的数列继续递推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1);
}
//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("请输入第%d号物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n");}
printf("请输入第%d号物品的价值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
//主函数
int main(int argc, char* argv[])
{ int i;
int num=0;//放入物品的数量
int weight=0;//背包可容纳的重量
float benefit=0;//总效益
stone *bag;//物品
/////输入背包可容纳的重量
do
{
printf("请输入背包可容纳的重量:");
scanf("%d",&weight);
if (weight<=0)
printf("背包可容纳的重量必须大于0!\n");
}while(weight<=0);
//输入物品种类
do
{
printf("请输入物品的数量:");
scanf("%d",&num);
if (num<=0)
printf("物品数量必须大于0!\n");
}while(num<=0);
bag=new stone[num];//物品数组
inputstone(bag,num);//输入物品的信息
sort(bag,num-1);//按单位效益排序
for(i=0;i<num&&weight>0;i++)
{
stone *temp=bag+i;
if(weight>=temp->weight)
{
weight-=temp->weight;
temp->weight=0;
benefit+=temp->benefit;
continue;
}
else
{
temp->weight-=weight;
weight=0;
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t));
break;
}
}
////////输出结果//////////
printf("物品种类 放入的比例 每单位效益 ");
for(i=0;i<num;i++)
{
stone *temp=bag+i;
printf("%d类物品",temp->name);
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);
printf(" %.4f\n",temp->benefit/(float)temp->weight_t);
}
printf("总效益:%.2f",benefit);
delete bag;
getchar();
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}