贪心算法买

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

LZ在开始研究ACM嘛？
#include<stdio.h>

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

B. pascal高手进！一道贪心算法——买票（求解题过程与解题思想）

贪心O(n)算法
var n,m,i,j,sum,max:longint;
a:array[0..1000010]of longint;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
i:=0;
j:=0;
sum:=0;
while j<n do
begin
sum:=sum-a[i];
inc(i);
while (j+1<=n)and(sum+a[j+1]<=m) do
begin
sum:=sum+a[j+1];
inc(j);
end;
if max<j-i+1 then max:=j-i+1;
end;
writeln(max);
end.

C. 收集各类贪心算法（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();
}

D. 一道贪心算法题目 一个人买卖商品，每天必须选择买或者卖，开始他的

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊会做了私戳我啊

E. 找零钱问题的贪心算法

问题描述：
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）
问题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱方案

F. 求c++程序（应该是贪心算法）急！！在线等！！！

使用a数组保存前i个元素的累加和，当a[j]-a[i]<=f时就表示可以购买i+1~j张连票。#include<iostream>
using namespace std;
int main()
{ int i,j,n,f,m=1,s,t,a[30]={0};
cin>>n>>f;
for(i=1;i<=n;i++)
{cin>>a[i];
a[i]+=a[i-1]; //a[i]:1~i张票价的总和
}
for(i=0;i<n;i++)
for(j=i;j<=n;j++)
if(a[j]-a[i]<=f&&j-i>m) //可以购买i+1~j张连票
m=j-i;
cout<<m<<' ';
return 0;
}

G. 骆驼商队问题（如何解决）贪心算法

典型tsp问题，目标函数变成利益最大化。如果城市很多很多，考虑使用pso或者遗传算法

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

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

I. 求贪心算法题（Pascal）

背包问题
program beibao;

const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;

procere init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;

procere make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;

begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.

旅行家问题
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procere buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procere solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.

n个部件,每个部件必须经过先A后B两道工序

program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procere init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procere sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procere playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procere calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.

没时间写了凑合着看看，履行承诺啊追加分数

J. 最少购物费用问题求解（贪心算法）

type struct
{ int code;
int quantity;
}elem
elem buy [b]//b所购商品的种类数

type struct
{elem data ;
float gprice;
}group;
group offer [m][s]//m表示优惠策略的组数，s表示每组中的商品数
float price[n] ;//n表示商品的种类数

Mincost(data buy [], group offer [m][],int s,int b int result[])
{ int p,i,j,k, remain[b],flag=1;float cost=0.0,min=0.0;
for(i=1;i<=s;i++)result[i]=0};
for(i=1;i<=b;i++) {min+=buy[i].quantity*price[buy[i].code]; //计算优惠前花费
remain[i]= buy[i].quantity;}
while(flag){
flag=0;
for(p=1;p<=m;p++)
{ if(Match(p)) {//判断本次购买与各个组合是否匹配
k=1;
for(i=1;i<=s;i++) {
while(buy[k].code<offer[p][i].data.code)k++;
if(buy[k].code==offer[p][i].data.code) {
remain[k] =buy[k].quantity-offer[p][i].data.quantity;//保存剩余数量
if(remain[k] >=2) flag=1;
k++; } }
cost=gprice[p];
for(i=1;i<=b;i++) cost+=remain[i] *price[buy[i].code];//优惠后花费
if(cost<min){cost=min; result[p]=1;}
}//endfor(p)
for(i=1;i<=b;i++)buy[i].quantity=remain[i];
}}

int Match(int k)
{
int i,j=1;
for(i=1;i<=s;i++) {
while(buy[j].code<offer[k][i].code&&j<=b)j++;
if(j>b)break;
if(buy[j].code==offer[k][i].code)
if( buy[j].quantity>=offer[k][i].quantity)
j++;
else break;
}
if(i>s)return 1;
else return 0;
}

这可是咱老师的答案