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語言 貪心演算法 小朋友分組 急急急急急急急 立刻！！！！！！！
int fun(int *a, int n, int MinC, int MaxC)
{
int pmin, pmax, smin, smax, i;
pmin = pmax = smin = smax = 0;
for(i=0; i<n; i++)
{
if(a[i] < MinC)pmin += (MinC - a[i]);
if(a[i] > MaxC)pmax += (a[i] - MaxC);
smin += (a[i] - MinC);
smax += (a[i] - MaxC);
}
if(pmin == pmax)return pmin;
if(pmin > pmax && smin > 0)return pmin;
if(pmax > pmin && smax < 0)return pmax;
return -1;
}
void main()
{
int a[] = {20,8,6};
printf("%d %d %d",fun(a,3,10,15),
fun(a,3,5,20),fun(a,3,1,2));
}
看一下fun函數行不行
⑶ 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語言，貪心演算法，貨幣找零問題
貪心演算法找零就是現實中從最大面額開始找的思路。不代表是最優解，只是演算法之一。
由於面額輸入順序不定，我先對輸入的面額進行降序排序。
下面代碼：
#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語言編程）經典題目
舉個例子,假如你買東西，老闆需要找給你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語言如何寫一個判斷貪心演算法不是最優解
所謂貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。
貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
為了證明不是最優解，就只能對0-1背包這類的進行枚舉了
⑺ 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;
}
⑻ C語言貪心演算法的問題
#include <stdio.h>
#define n 7 //有多少個物品種類
struct goods //定義物品的各個屬性
{
int x; //物品放入背包的重量
int order; //物品編號
int p; //物品總價值
int w; //物品總重量
};
int Strategy1(struct goods goods[],int m) //策略一：按物品重量降序裝包
{
struct goods temp;
float value=0;
int i,j,k=0;
for(i=0;i<n-1;i++) //按照物品總價值降序排列（上面不是說要按重量排序嗎？n怎麼沒定義？）
{
for(j=i+1;j<n;j++)
{
if(goods[j].p>goods[i].p)
{
temp=goods[i];
goods[i]=goods[j];
goods[j]=temp;
}
}
}
for(;k<n;k++) //開始裝包
{
if(goods[k].w>m)
break;
goods[k].x=goods[k].w;
m-=goods[k].w; //（看程序m應該是重量限制吧！前三個裝包已經超重了，第四個當然 就沒法裝包了啊）
value+=goods[k].p;
}
if(k<n)
{
goods[k].x=m;
value=((float)m/goods[k].w)*goods[k].p;
}
printf("這是策略一的結果:\n"); //輸出結果
for(i=0;i<n;i++)
{
printf("商品%d有%f放入背包\n",goods[i].order,(float)(goods[i].x/goods[i].w));
}
printf("商品的總價值為%f",value);
return value;
}
void main()
{
float value1;
struct goods goods[7]={0,1,10,2,0,2,5,3,0,3,15,5,0,4,7,7,0,5,6,1,0,6,18,4,0,7,3,1};
int m=15;
value1=Strategy1(goods,m);
⑼ c語言貪心演算法的問題
內容我沒看
但是你最後是不是多了一個endl？
cout<<endl<<"Number of fish expected:"<<' '<<maxn<<endl;
⑽ 五大常用演算法之一：貪心演算法
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，換句話說，當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。這是貪心演算法可行的第一個基本要素。貪心演算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。 對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心演算法求解的關鍵特徵。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。比如， 求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法 。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
貪心策略：選取價值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優先裝重量小的,這樣的問題就可以解決.
所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）。