貪心演算法實例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));