貪心演算法買

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

這可是咱老師的答案