Ⅰ 很簡單的C語言貪心演算法，用map做的，但我對map有個問題
C語言作為計算機最重要的一種語言，關於它的資料是不計其數的。我早看夠了Turbo C那個環境。
我剛剛下載了一個用於C 語言的windows編譯環境wintc191 ，它比Turbo C要好很多的。實在是太棒了！軟體主要特色：
1.在WINDOWS下編輯TC代碼，可以充分利用WINDOWS的支持剪貼版和中文的特點
2.Include和Lib路徑自動定位，告別TC設置路徑的歷史
3.編譯錯誤捕捉功能，編譯時不會出現煩人的DOS窗口
4.支持C內嵌匯編從而實現C/ASM混合編程
5.支持C擴展庫（自定義LIB庫）
6.錯誤警告定位功能、出現編譯錯誤時雙擊輸出框里的出錯行信息可以自動尋找到錯誤的行，就像DOS的TC那樣
7.支持語法加亮功能，並可以自定義設置
8.沒有目錄路徑限制，你甚至可以安裝到帶有空格的路徑文件夾里
9.允許自定義設置輸入風格，能夠實現VC類似的輸入風格
10.可選擇是否生成ASM、MAP或OBJ文件，你甚至可以指定只生成EXE文件
11.穩定的文件操作功能，支持歷史記錄列表和使用模板
12.撤消和重復功能，並可以按照自己內存情況設置最多撤消次數（最多允許999次）
13.具有行標計數的功能，並可以設置樣式
該軟體的下載地址是： 直接雙擊這個地址就可以下載了。這個地址我剛剛試過的，所以我只給了你這一個地址。
C語言學習系統是有很多的版本的，可以在「迅雷」裡面搜索。當然很多的免費的學習系統比那些需要注冊的還要好很多的。晨輝的那個學習系統我個人感覺不怎麼樣，建議你在一些專業的C語言學習網站上去找一個更好的吧。
另外,團IDC網上有許多產品團購,便宜有口碑
Ⅱ 求解一道貪心演算法
因為這個問題涉及到高維求解（大於3維），所以不推薦你用貪心演算法或遺傳演算法之類的演算法。這里給出一種升級的蒙特卡羅演算法——自適應序貫數論演算法，這是一種以GLP集合為基礎的隨機遍歷演算法，可以很輕易的解決一系列的高維求解問題，目前根據網上能找到的資料最多可以做到18維。
下面就根據你給出的例子講解一下：
對於6000的料來說
1185最多做到5根（要求4根，所以一根木料對於1185的產品來說最多有0到45種可能）；1079最多做到5根；985最多做到6根；756最多做到7根。
所以第一次加工一根木料最多有5*6*7*8=1680種加工可能（當然其中包括那些產品總長度大於料長的可能，但是我們可以通過罰函數來避免這些情況），那麼利用GLP演算法我們可以一次性產生這1680種可能，然後逐個比較那種可能最省木料；
設第一加工出的產品量分別為1 1 3 1
那麼1185加工量剩3，1079剩5，985剩7，756剩7，所以第二次加工的可能性有（3+1）*（5+1）*（6+1）*（7+1）=1120種
關於自適應序貫數論演算法，根據這道題你可以這樣理解，4種尺寸構成了一個4維的空間，四種尺寸的每一種組合相當於空間中的一個點（1185的1根，1079的1根，985的3根，756的1根，這就組成了這個4維空間中的(1,1,3,1)點) ，自適應序貫數論演算法就是先根據GLP演算法在這個4維空間中隨機的，均勻的分布一定的點（也就是尺寸的組合），然後根據目標函數確定其中哪一個點是最優點，我們認為最優點的附近出現最優解的可能性最大，那麼我們就以最優點為中心，以一定的尺度為半徑將原空間縮小，然後我們在心空間中再一次利用GLP演算法均勻，隨機的充滿這個空間，然後重復以上過程，直到這個空間小到我們事先規定的大小，這樣我們就找到了最優解。
也許你會擔心演算法一上來就收斂到了局部最優解，然後一直在這里打轉，不用擔心，GLP最大的優點就是均勻的充斥整個空間，盡量將每一種可能都遍歷到。
這種演算法的缺點在於充斥空間用的點需要生成向量來生成，每一種充斥方式都需要不同的向量，你可以在《數論方法在統計中的應用》這本書中查到已有的每種充斥方式對應的那些生成向量。
下面是我跟據對你給出的例子的理解算出的結果。
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:0根
985:1根
756:5根
剩餘木料15
1185:0根
1079:3根
985:0根
756:0根
剩餘木料2748
用去木料：5根
請按任意鍵繼續. . .
程序代碼如下：（變數都是用漢語拼音標的）
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <fstream.h>
#include <windows.h>
#include "glp.h"
#define jiedeweishu 4
#define glpgeshu 10007
#define glpgeshu1 5003//100063
#define glpgeshu2 6007//33139//71053//172155//100063
#define yuanmuchang 6000
#define qiegesushi 5
#define chicun1 1185
#define chicun2 1079
#define chicun3 985
#define chicun4 756
#define chicun1shuliang 4
#define chicun2shuliang 6
#define chicun3shuliang 10
#define chicun4shuliang 8
float xuqiuchicun[jiedeweishu]={chicun1,chicun2,chicun3,chicun4};
float chicunxuqiuliang[jiedeweishu]={chicun1shuliang,chicun2shuliang,chicun3shuliang,chicun4shuliang};
float zuobianjie0[jiedeweishu];//{-19,1,-11,1.5,0,200};//{0.39111,-18.5,1,-11,1,0,2};//左邊界
float youbianjie0[jiedeweishu];//{-17,1.5,-7,2,0.05,900};//{0.393,-17,2,-9,2,0.1,6};//右邊界
float zuobianjie[jiedeweishu];
float youbianjie[jiedeweishu];
float zuobianjie1[jiedeweishu];//過度用
float youbianjie1[jiedeweishu];
float zuobianjie2[jiedeweishu];//局部邊界
float youbianjie2[jiedeweishu];
float zuobianjie3[jiedeweishu];//大邊界
float youbianjie3[jiedeweishu];
float sheng_cheng_xiang_liang[jiedeweishu]={1,1206,3421,2842};//生成向量
float sheng_cheng_xiang_liang1[jiedeweishu]={1,792,1889,191};//{1,39040,62047,89839,6347,30892,64404};//生成向量
float sheng_cheng_xiang_liang2[jiedeweishu]={1,1351,5080,3086};//{1,18236,1831,19143,5522,22910};//{1,18010,3155,50203,6065,13328};//{1,167459,153499,130657,99554,61040,18165};
struct chushi
{
float geti[jiedeweishu];
float shiying;
};
chushi *zuiyougeti;//精英保存策略
chushi *zuiyougetijicunqi;
int sishewuru(float);
float cha;//左右邊界的差
int biao;//判斷尋優是否成功1表示成功0表示不成功
int maxgen;//最大計算代數
int gen;//目前代數
void initialize();//演算法初始化
void jingyingbaoliu();//精英保存的實現
void mubiaohanshu1(chushi &bianliang);//適應度的計算使用殘差法
int cmpshiyingjiang(const void *p1,const void *p2)
{
float i=((chushi *)p1)->shiying;
float j=((chushi *)p2)->shiying;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}
int cmp1(const void *p1,const void *p2)
{
float i= *(float*)p1;
float j= *(float*)p2;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}
void main()
{
float bianjiebianhuashuzu[jiedeweishu];
float yiwanchengshuliang[jiedeweishu];
zuiyougeti=new chushi;//最優個體的生成
zuiyougetijicunqi=new chushi;
int i;
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=0;
yiwanchengshuliang[i]=0;
}
int muliaoshuliang=0;
while(1)
{
if(yiwanchengshuliang[0]==chicun1shuliang&&yiwanchengshuliang[1]==chicun2shuliang&&yiwanchengshuliang[2]==chicun3shuliang&&yiwanchengshuliang[3]==chicun4shuliang)
break;//都加工完了就退出程序
biao=1;
for(i=0;i<jiedeweishu;i++)
{
bianjiebianhuashuzu[i]=chicunxuqiuliang[i]-yiwanchengshuliang[i];
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie0[i]=0;
if(bianjiebianhuashuzu[i]>(int)(yuanmuchang/xuqiuchicun[i]))
{
youbianjie0[i]=(int)(yuanmuchang/xuqiuchicun[i]);
}
else
{
youbianjie0[i]=bianjiebianhuashuzu[i];
}
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie[i]=zuobianjie0[i];
youbianjie[i]=youbianjie0[i];
}
for(i=0;i<jiedeweishu;i++)//在這套程序中邊界分為兩個部分,其中一組是根據最優解的收斂范圍進行局部尋優,如果在局部找不到最優解則以現有最優解為中心進行全局搜索
{
zuobianjie2[i]=zuobianjie[i];
youbianjie2[i]=youbianjie[i];
zuobianjie3[i]=zuobianjie[i];
youbianjie3[i]=youbianjie[i];
}
zuiyougeti->shiying=-3000;
//cout<< zuiyougeti->shiying<<endl;
initialize();
//for(i=0;i<jiedeweishu;i++)/////
//{////
// cout<<zuiyougeti->geti[i]<<",";////
//}/////////
//cout<<endl;/////
// cout<<"初始最優解："<<" "<<-zuiyougeti->shiying<<endl;/////////////
for(gen=1;gen<maxgen;gen++)
{
jingyingbaoliu();
if(cha<1e-1)
break;
}
//cout<<"最終在收斂的范圍內左右邊界的最大差值: "<<cha<<endl;
//for(i=0;i<jiedeweishu;i++)
//{
// cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti[i]<<",";
// }
//cout<<endl;
//cout<<"共用代數"<<gen<<endl;
cout<<"1185:"<<zuiyougeti->geti[0]<<"根"<<endl;
cout<<"1079:"<<zuiyougeti->geti[1]<<"根"<<endl;
cout<<"985:"<<zuiyougeti->geti[2]<<"根"<<endl;
cout<<"756:"<<zuiyougeti->geti[3]<<"根"<<endl;
cout<<"剩餘木料"<<(-zuiyougeti->shiying)<<endl;////////////////
cout<<endl;
for(i=0;i<jiedeweishu;i++)
{
yiwanchengshuliang[i]=yiwanchengshuliang[i]+zuiyougeti->geti[i];
}
muliaoshuliang++;
}
cout<<"用去木料："<<muliaoshuliang<<"根"<<endl;
delete [] zuiyougetijicunqi;
delete [] zuiyougeti;
system("pause");
}
void initialize()
{
maxgen=20;//最大代數
gen=0;//起始代
cha=100;
chushi *chushizhongqunji;
chushizhongqunji=new chushi[glpgeshu];
int i,j;
for(i=0;i<jiedeweishu;i++)
{
zuobianjie1[i]=zuobianjie[i];
youbianjie1[i]=youbianjie[i];
}
float **glp_shu_zu;//第一次求解，為了使解更精確這一次求解需要的點最多
glp_shu_zu=new (float *[glpgeshu]);
for(i=0;i<glpgeshu;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpgeshu,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,sheng_cheng_xiang_liang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
for(i=0;i<glpgeshu;i++)//產生初始種群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
if(j==3&&glp_shu_zu[i][j]<0)
{
cout<<"274"<<endl;/////////////
cout<<zuobianjie[j]<<" "<<glp_shu_zu[i][j]<<" "<<youbianjie[j]<<endl;////////////////////
system("pause");///////////////////
}
}
}
for(i=0;i<glpgeshu;i++)//計算初始種群的適應度
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpgeshu,sizeof(chushi),&cmpshiyingjiang);//根據適應度將初始種群集按降序進行排列
chushi *youxiugetiku;//建立一個儲存優秀個體的庫
youxiugetiku=new chushi[glpgeshu];//建立一個儲存優秀個體的庫
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougeti->shiying)//凡是比上一代的最優個體還要好的個體都放入優秀個體庫
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
//cout<<youxiugetiku[i].geti[j]<<endl;
}
//system("pause");
i++;
}
// cout<<i<<endl;//////////////
//system("pause");//////////////////////////////////////
jishuqi=i;//將得到的優秀個體的數量放入jishuqi保存
float *bianjiezancunqi;//下面就要以優秀個體庫中個體的范圍在成立一個局部搜索區域，所以先建立一個邊界暫存器
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];//將優秀個體庫每一維的數據都放入bianjiezancunqi
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);//對這些數據按降序排列，取兩個邊界又得到一個局部范圍
//將得到的范圍進行保存
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
//cout<<zuobianjie[i]<<endl;//////////////////////////
// cout<<youbianjie[i]<<endl;///////////////////////////
//cout<<endl;///////////////////
//
if(zuobianjie[i]<zuobianjie2[i])//如果新得到的局部左邊界在上一代局部左邊界左邊，則左邊界取上一代的
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])//如果新得到的局部右邊界在上一代局部右邊界右邊，則右邊界取上一代的
{
youbianjie[i]=youbianjie2[i];
}
}
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)//本代種群的最優個體比歷史最有個個體好，則用本代的代替之，並將標志位賦值為1表示尋優成功
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
for(i=0;i<glpgeshu;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;
}
void jingyingbaoliu() //精英保留的實現
{
float glpshuliang,xiangliang[jiedeweishu];
if(biao==1)//如果尋優成功則利用局部搜索的數據
{
glpshuliang=glpgeshu1;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i];
}
}
else//否則利用全局搜索的數據
{
glpshuliang=glpgeshu2;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang2[i];
}
}
chushi *chushizhongqunji;//建立一個用來儲存種群的容器
chushizhongqunji=new chushi[glpshuliang];
int i,j;
float **glp_shu_zu;//生成一個glp數組
glp_shu_zu=new (float *[glpshuliang]);
for(i=0;i<glpshuliang;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpshuliang,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,xiangliang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
//cout<<"377"<<endl;
if(biao!=1)//如果尋優不成功則進入全局搜索
{
//cout<<"380"<<endl;////////////
float bianjiecha[jiedeweishu];
for(i=0;i<jiedeweishu;i++)
{
bianjiecha[i]=youbianjie3[i]-zuobianjie3[i];//計算上一代全局每一維范圍的寬度
}
static float rou=0.9;//定義收縮比
//float rou=pow(0.5,gen);
for(i=0;i<jiedeweishu;i++)//確定新的范圍
{
zuobianjie1[i]=zuiyougeti->geti[i]-rou*bianjiecha[i];//左邊界為以最優個體為中心-范圍寬度乘以收縮比
if(zuobianjie1[i]>zuobianjie2[i])//如果新的左邊界比目前局部左邊界大，那麼以目前的為全局尋優的左邊界
{
zuobianjie[i]=zuobianjie1[i];
zuobianjie3[i]=zuobianjie1[i];
}
else//否則以局部左邊界為全局左邊界
{
zuobianjie[i]=zuobianjie2[i];
zuobianjie3[i]=zuobianjie2[i];
}
youbianjie1[i]=zuiyougeti->geti[i]+rou*bianjiecha[i];//右邊界為以最優個體為中心+范圍寬度乘以收縮比
if(youbianjie1[i]<youbianjie2[i])
{
youbianjie[i]=youbianjie1[i];
youbianjie3[i]=youbianjie1[i];
}
else
{
youbianjie[i]=youbianjie2[i];
youbianjie3[i]=youbianjie2[i];
}
}
qsort(bianjiecha,jiedeweishu,sizeof(float),&cmp1);
if(cha==bianjiecha[0])//如果最大邊界差不變的話就將收縮因子變小
{
rou=pow(rou,2);
}
cha=bianjiecha[0];
}
//cout<<"421"<<endl;/////////////////////
for(i=0;i<glpshuliang;i++)//根據新產生的最優個體確定glp群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
}
}
for(i=0;i<glpshuliang;i++)
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpshuliang,sizeof(chushi),&cmpshiyingjiang);
zuiyougetijicunqi->shiying=zuiyougeti->shiying;
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
else
{
// cout<<"446"<<endl;/////////////
biao=0;
}
if(biao==1)//如果尋優成功了就需要確立一個新的局部最優解范圍
{
chushi *youxiugetiku;
youxiugetiku=new chushi[glpshuliang];
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougetijicunqi->shiying)
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
}
i++;
}
jishuqi=i;
float *bianjiezancunqi;
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
// cout<<zuobianjie[i]<<endl;//////////////
// cout<<youbianjie[i]<<endl;/////////////
// cout<<endl;///////////////
if(zuobianjie[i]<zuobianjie2[i])
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])
{
youbianjie[i]=youbianjie2[i];
}
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
}
for(i=0;i<glpshuliang;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;
}
void mubiaohanshu1(chushi &bianliang)//計算shiying
{
int i=0;
int sunshi,chanpin;
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]-1);
chanpin=chicun1*bianliang.geti[0]+chicun2*bianliang.geti[1]+chicun3*bianliang.geti[2]+chicun4*bianliang.geti[3];
bianliang.shiying=yuanmuchang-sunshi-chanpin;
if(bianliang.shiying!=0)//如果不能正好將木料分成所需尺寸則要多切一刀
{
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]);
}
if(bianliang.shiying<0)//罰函數
{
bianliang.shiying=bianliang.shiying+1e5;
}
bianliang.shiying=-bianliang.shiying;
}
int sishewuru(float x)
{
float y;
int z;
y=x-(int)x;
if(y<0.5)
{
z=(int)(x);
}
else
{
z=(int)x;
z=z+1;
}
return z;
}
glp.h源文件貼不下了，把你郵箱給我我發給你
郵箱：[email protected]
Ⅲ 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;
}
Ⅳ 關於編程的貪心法
定義
所謂貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。 貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
[編輯本段]貪心演算法的基本思路
1.建立數學模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解，得到子問題的局部最優解。 4.把子問題的解局部最優解合成原來解問題的一個解。 實現該演算法的過程： 從問題的某一初始解出發； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解。 下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。
[編輯本段]例題分析
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30 分析： 目標函數： ∑pi最大 約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150) （1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？ （2）每次挑選所佔重量最小的物品裝入是否能得到最優解？ （3）每次選取單位重量價值最大的物品，成為解本題的策略。 值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。 貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。 可惜的是，它需要證明後才能真正運用到題目的演算法中。 一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。 對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下： （1）貪心策略：選取價值最大者。 反例： 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，則答案錯誤。 【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】 對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。 但是，如果題目是如下所示，這個策略就也不行了。 W=40 物品：A B C 重量：28 20 15 價值：28 20 15 附：本題是個NP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
[編輯本段]備注
貪心演算法當然也有正確的時候。求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法。 所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）
[編輯本段]附貪心演算法成功案例之一
馬踏棋盤的貪心演算法 123041-23 XX 【問題描述】 馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。 【初步設計】 首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下： 1、 輸入初始位置坐標x,y； 2、 步驟 c: 如果c> 64輸出一個解，返回上一步驟c-- (x,y) ← c 計算(x,y)的八個方位的子結點，選出那此可行的子結點 循環遍歷所有可行子結點，步驟c++重復2 顯然（2）是一個遞歸調用的過程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//輸入一個解 return; }
Ⅳ C語言問題2
我將上面的程序改成了如下程序：
1 #include <stdio.h>
2 func(int a,int b)
3 {return a+b;}
4
5 int main()
6 {
7 int x=6,y=7,z,j,k;
8 z=func(j=func(x++,y++),k=func(--x,--y));
9 printf("%d\t%d\t%d\n",j,k,z);
10 }
THE KEY：11 、11、 22。
程序運行的結果之所以會是這樣：是C的++X和X++、--X和X--編譯執行不同。
建議了解C的自加（減），C程序的運行。
Ⅵ 求C語言高手 多機調度問題 ，設計個程序 要C語言版的 不要C++的 謝謝啊
#include<stdio.h>
#define N 10
typedef struct node
{
int ID,time;
}jobnode;
typedef struct Node
{
int ID,avail;
}manode;
manode machine[N];
jobnode job[N];
manode* Find_min(manode a[],int m)
{
manode* temp=&a[0];
for(int i=1;i<m;i++)
{
if(a[i].avail<temp->avail)
temp=&a[i];
}
return temp;
}
void Sort(jobnode t[],int n)
{
jobnode temp;
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
{
if(job[j].time>job[j-1].time)
{
temp=job[j];
job[j]=job[j-1];
job[j-1]=temp;
}
}
}
void main()
{
int n,m,temp;
manode* ma;
printf("輸入作業數目(作業編號按輸入順序處理)\n");
scanf("%d",&n);
printf("輸入相應作業所需處理時間:\n");
for(int i=0;i<n;i++)
{
scanf("%d",&job[i].time);
job[i].ID=i+1;
}
printf("輸入機器數目(機器編號按輸入順序處理)\n");
scanf("%d",&m);
for(i=0;i<m;i++)
{
machine[i].ID=i+1;
machine[i].avail=0;
}
putchar('\n');
if(n<=m)
{
printf("為每個作業分配一台機器,可完成任務!\n");
return;
}
Sort(job,n);
for(i=0;i<n;i++)
{
ma=Find_min(machine,m);
printf("將機器: %d 從 %d -----> %d 的時間段分配給作業: %d\n",ma->ID,ma->avail,ma->avail+job[i].time,job[i].ID);
ma->avail+=job[i].time;
}
temp=machine[0].avail;
for(i=1;i<m;i++)
{
if(machine[i].avail>temp)
temp=machine[i].avail;
}
putchar('\n');
printf("該批作業處理完成所需加工時間為: %d\n",temp);
}
剛寫的，試過了，運行通過．主要運用貪心演算法，應該算比較典型的吧，呵呵，該睡覺了，明天還有考試呢，希望對你有幫助！共同進步哈！
Ⅶ C++貪心演算法
將所有的區間按左端點從小到大排序，依次順序處理每個區間。每次選擇覆蓋點S的區間中右端點坐標最大的一個，並將S更新為該區間的右端點坐標，直到選擇的區間已包含了F為止。
Ⅷ 最佳調度問題（c/c++）
如果各機器運行速度相等，換句話就是任務無論在哪台機器上運行完成時間都相等，則問題較簡單
1 . 先將任務由大到小排序
2 . 計算n個任務需要的總時間和平均到k個機器上的時間
3 . 將大於平均時間的任務各分配一個機器，找到最大完成時間
4 . 將其他任務順序安排在一台機器上，如果時間超出最大時間，則把該任務交給下一個機器，下一個任務繼續在這台機器上試安排，直到所有任務都不能在小於最大完成時間的情況下安排
5 . 安排下一台機器直道所有任務安排完，
6 . 或有可能安排某(些)任務找不到小於最大完成時間 那麼重新掃描各台機器使再加上該任務後時間最小，按此方法安排萬所有任物
數據結構採用鏈表比較合適，
K個機器k個鏈，n個任務按大小順序插入一個鏈表，安排後從任務鏈表中移動到機器鏈表中。知道鏈表為空
Ⅸ 求C語言或c++的貪心演算法的例題
比如：
int a=3,b=4,c;
c=a+++b;
將被解釋為
c=(a++)+b;
而不會被解釋為
c=a+(++b);
貪心演算法的主要意義是從左至右依次解釋最多的符號！
Ⅹ 收集各類貪心演算法（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();
}