貪心演算法的應用
Ⅰ 貪心演算法的數學應用
如把3/7和13/23分別化為三個單位分數的和
【貪心演算法】
設a、b為互質正整數，a<b 分數a/b 可用以下的步驟分解成若干個單位分數之和：
步驟一： 用b 除以a，得商數q1 及余數r1。（r1=b - a*q1）
步驟二：把a/b 記作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步驟三：重復步驟2，直到分解完畢
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其實是數學家斐波那契提出的一種求解埃及分數的貪心演算法，准確的演算法表述應該是這樣的：
設某個真分數的分子為a，分母為b;
把b除以a的商部分加1後的值作為埃及分數的某一個分母c；
將a乘以c再減去b，作為新的a；
將b乘以c，得到新的b；
如果a大於1且能整除b，則最後一個分母為b/a；演算法結束；
或者，如果a等於1，則，最後一個分母為b；演算法結束；
否則重復上面的步驟。
備註：事實上，後面判斷a是否大於1和a是否等於1的兩個判斷可以合在一起，及判斷b%a是否等於0，最後一個分母為b/a，顯然是正確的。
PHP代碼： classtanxin{public$weight;public$price;publicfunction__construct($weight=0,$price=0){$this->weight=$weight;$this->price=$price;}}//生成數據$n=10;for($i=1;$i<=$n;$i++){$weight=rand(1,20);$price=rand(1,10);$x[$i]=newtanxin($weight,$price);}//輸出結果functiondisplay($x){$len=count($x);foreach($xas$val){echo$val->weight,'',$val->price;echo'<br>';}}//按照價格和重量比排序functiontsort(&$x){$len=count($x);for($i=1;$i<=$len;$i++){for($j=1;$j<=$len-$i;$j++){$temp=$x[$j];$res=$x[$j+1]->price/$x[$j+1]->weight;$temres=$temp->price/$temp->weight;if($res>$temres){$x[$j]=$x[$j+1];$x[$j+1]=$temp;}}}}//貪心演算法functiontanxin($x,$totalweight=50){$len=count($x);$allprice=0;for($i=1;$i<=$len;$i++){if($x[$i]->weight>$totalweight)break;else{$allprice+=$x[$i]->price;$totalweight=$totalweight-$x[$i]->weight;}}if($i<$len)$allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);return$allprice;}tsort($x);//按非遞增次序排序display($x);//顯示echo'0-1背包最優解為:';echotanxin($x);java源代碼 packagemain;importjava.util.ArrayList;importjava.util.Collections;importjava.util.Comparator;importjava.util.List;importjava.util.Random;publicclassMain{/***測試*/publicstaticvoidmain(String[]args){//1.隨機構造一批任務List<Pair<Integer>>inputList=newArrayList<Pair<Integer>>();Randomrand=newRandom();for(intn=0;n<20;++n){Integerleft=rand.nextInt(100);Integerright=left+rand.nextInt(100)+1;Pair<Integer>pair=newPair<Integer>(left,right);inputList.add(pair);}//將任務列表按結束時間排序（也就是根據right欄位進行排序）sortByRight(inputList);printPairList(inputList);//執行演算法List<Pair<Integer>>outputList=algorithm(inputList);System.out.println();printPairList(outputList);}/***貪心演算法**@paraminputList*@return使數量最多的任務方案*/publicstatic<TextendsComparable<T>>List<Pair<T>>algorithm(List<Pair<T>>inputList){if(null==inputList||inputList.size()==0||inputList.size()==1){returninputList;}sortByRight(inputList);List<Pair<T>>outputList=newArrayList<Pair<T>>();intlast=0;outputList.add(inputList.get(last));intintputSize=inputList.size();for(intm=1;m<intputSize;++m){Pair<T>nextPair=inputList.get(m);TnextLeft=nextPair.getLeft();Pair<T>lastOutPair=inputList.get(last);TlastRight=lastOutPair.getRight();intflag=nextLeft.compareTo(lastRight);if(flag>=0){outputList.add(nextPair);last=m;}}returnoutputList;}/***對傳入的List<Pair<T>>對象進行排序，使Pair根據right從小到大排序。**@paraminputList*/privatestatic<TextendsComparable<T>>voidsortByRight(List<Pair<T>>inputList){CompareByRight<T>comparator=newCompareByRight<T>();Collections.sort(inputList,comparator);}/***列印一個List<Pair<T>>對象。**@paraminputList*/privatestatic<TextendsComparable<T>>voidprintPairList(List<Pair<T>>inputList){for(Pair<T>pair:inputList){System.out.println(pair.toString());}}}/***根據Pair.right比較兩個Pair。用於Conlections.sort()方法。**@param<T>*/classCompareByRight<TextendsComparable<T>>implementsComparator<Pair<T>>{/*@Override*/publicintcompare(Pair<T>o1,Pair<T>o2){Tr1=o1.getRight();Tr2=o2.getRight();intflag=r1.compareTo(r2);returnflag;}}/***代表一個任務對象。有點裝逼用模板來寫了。left表示開始時間，right表示結束時間。**@param<T>*/classPair<TextendsComparable<T>>{privateTleft;privateTright;publicPair(Tleft,Tright){this.left=left;this.right=right;}@OverridepublicStringtoString(){return[left=+left.toString()+','+right=+right.toString()+']';}publicTgetLeft(){returnleft;}publicvoidsetLeft(Tleft){this.left=left;}publicTgetRight(){returnright;}publicvoidsetRight(Tright){this.right=right;}}
Ⅱ 求解一道貪心演算法
因為這個問題涉及到高維求解（大於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]
Ⅲ 求貪心演算法題（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.
沒時間寫了湊合著看看，履行承諾啊追加分數
Ⅳ 怎樣應用貪心演算法求得最優解
動態規劃要求。。具有最優子結構，記f[i]最優時，f[i - 1]的解也最優。。。最終可以得到最優解
貪心演算法，一般只能得到近優解或者局部最優解。。
Ⅳ Pascal貪心演算法，求解答！
這道題用貪心不大好吧
記得老師以前說過
這種題用DP
這道題是最簡單的01背包
我給你發個資料
那個，發不了啊，上傳失敗
你給我qq吧
P01: 01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
注意f[i][v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢後，最終的答案並不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態的定義中的「恰」字去掉，在轉移方程中就要再加入一項f[i][v-1]，這樣就可以保證f[N] [V]就是最後的答案。至於為什麼這樣就可以，由你自己來體會了。
優化空間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i -1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
總結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。
P02: 完全背包問題
題目
有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本思路
這個問題非常類似於01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}。這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間則不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。
將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。
一個簡單有效的優化
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。
轉化為01背包問題求解
既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c [i]件，於是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。
更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。 但我們有更優的O(VN)的演算法。 * O(VN)的演算法 這個演算法使用一維數組，先看偽代碼： <pre class"example"> for i=1..N for v=0..Vf[v]=max{f[v],f[v-c[i]]+w[i]};
你會發現，這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮「選入第i件物品」這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮「加選一件第i種物品」這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須採用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。
這個演算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個方程用一維數組實現，便得到了上面的偽代碼。
總結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在「基本思路」以及「O(VN)的演算法「的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。
P03: 多重背包問題
題目
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本演算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對於第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}。復雜度是O(V*∑n[i])。
轉化為01背包問題
另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為∑n[i]的01背包問題，直接求解，復雜度仍然是O(V*∑n[i])。
但是我們期望將它轉化為01背包問題之後能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價於取若干件代換以後的物品。另外，取超過n[i]件的策略必不能出現。
方法是：將第i種物品分成若干件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分別為 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種物品分成系數分別為1,2,4,6的四件物品。
分成的這幾件物品的系數和為n[i]，表明不可能取多於n[i]件的第i種物品。另外這種方法也能保證對於0..n[i]間的每一個整數，均可以用若干個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，並不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉化為了復雜度為O(V*∑logn[i])的01背包問題，是很大的改進。
O(VN)的演算法
多重背包問題同樣有O(VN)的演算法。這個演算法基於基本演算法的狀態轉移方程，但應用單調隊列的方法使每個狀態的值可以以均攤O(1)的時間求解。由於用單調隊列優化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的「男人八題」幻燈片上。
小結
這里我們看到了將一個演算法的復雜度由O(V*∑n[i])改進到O(V*∑log n[i])的過程，還知道了存在應用超出NOIP范圍的知識的O(VN)演算法。希望你特別注意「拆分物品」的思想和方法，自己證明一下它的正確性，並用盡量簡潔的程序來實現。
P04: 混合三種背包問題
問題
如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎麼求解呢？
01背包與完全背包的混合
考慮到在P01和P02中最後給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那麼只需在對每個物品應用轉移方程時，根據物品的類別選用順序或逆序的循環即可，復雜度是O(VN)。偽代碼如下：
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
再加上多重背包
如果再加上有的物品最多可以取有限次，那麼原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的演算法的話，用P03中將每個這類物品分成O(log n[i])個01背包的物品的方法也已經很優了。
小結
有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什麼難題，但將它們簡單地組合起來以後就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。
P05: 二維費用的背包問題
問題
二維費用的背包問題是指：對於每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對於每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a[i]和b[i]。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w[i]。
演算法
費用加了一維，只需狀態也加一維即可。設f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態轉移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數組：當每件物品只可以取一次時變數v和u採用順序的循環，當物品有如完全背包問題時採用逆序的循環。當物品有如多重背包問題時拆分物品。
物品總個數的限制
有時，「二維費用」的條件是以這樣一種隱含的方式給出的：最多隻能取M件物品。這事實上相當於每件物品多了一種「件數」的費用，每個物品的件數費用均為1，可以付出的最大件數費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最後在f[0..V][0..M]范圍內尋找答案。
另外，如果要求「恰取M件物品」，則在f[0..V][M]范圍內尋找答案。
小結
事實上，當發現由熟悉的動態規劃題目變形得來的題目時，在原來的狀態中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。
P06: 分組的背包問題
問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
演算法
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬於第k組}。
使用一維數組的偽代碼如下：
for 所有的組k
for 所有的i屬於組k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}
另外，顯然可以對每組中的物品應用P02中「一個簡單有效的優化」。
小結
分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義「泛化物品」的概念，十分有利於解題。
P07: 有依賴的背包問題
簡化的問題
這種背包問題的物品間存在某種「依賴」的關系。也就是說，i依賴於j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴於別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。
演算法
這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴於別的物品的物品稱為「主件」，依賴於某主件的物品稱為「附件」。由這個問題的簡化條件可知所有的物品由若干主件和依賴於每個主件的一個附件集合組成。
按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件後再選擇一個附件，選擇主件後再選擇兩個附件……無法用狀態轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數級。）
考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應於P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應於這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化並不能給出一個好的演算法，因為物品組中的物品還是像原問題的策略一樣多。
再考慮P06中的一句話： 可以對每組中的物品應用P02中「一個簡單有效的優化」。這提示我們，對於一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的「附件集合」先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]。那麼這個主件及它的附件集合相當於V-c[i]+1個物品的物品組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數級的策略中有很多策略都是冗餘的，通過一次01背包後，將主件i轉化為 V-c[i]+1個物品的物品組，就可以直接應用P06的演算法解決問題了。
更一般的問題
更一般的問題是：依賴關系以圖論中「森林」的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多隻依賴於一個物品（只有一個主件）且不出現循環依賴。
解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由於附件可能還有附件，就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。
事實上，這是一種樹形DP，其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了「泛化物品」的思想。看完P08後，你會發現這個「依賴關系樹」每一個子樹都等價於一件泛化物品，求某節點為根的子樹對應的泛化物品相當於求其所有兒子的對應的泛化物品之和。
小結
NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。後來我通過思考發現通過引入「物品組」和「依賴」的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價於一個由四個物品組成的物品組，這便揭示了問題的某種本質。
我想說：失敗不是什麼丟人的事情，從失敗中全無收獲才是。
P08: 泛化物品
定義
考慮這樣一種物品，它並沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。
更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數的函數h，當分配給它的費用為v時，能得到的價值就是h(v)。
這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數組h[0..V]，給它費用v，可得到價值h[V]。
一個費用為c價值為w的物品，如果它是01背包中的物品，那麼把它看成泛化物品，它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品，那麼它可以看成這樣一個函數，僅當v被c整除時有h(v)=v/c*w，其它函數值均為0。如果它是多重背包中重復次數最多為n的物品，那麼它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n，其它情況函數值均為0。
一個物品組可以看作一個泛化物品h。對於一個0..V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價於一個物品組，自然也可看作一個泛化物品。
泛化物品的和
如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎麼求呢？事實上，對於一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對於0..V的每一個整數v，可以求得費用v分配到h和l中的最大價值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一個由泛化物品h和l決定的定義域為0..V的函數，也就是說，f是一個由泛化物品h和 l決定的泛化物品。
由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間復雜度是O(V^2)。
泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對於其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。
背包問題的泛化物品
一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能將問題對應於某個泛化物品。也就是說，給定了所有條件以後，就可以對每個非負整數v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關於問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之後，就可以根據這個函數的取值得到背包問題的最終答案。
綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然後求之。
小結
本講可以說都是我自己的原創思想。具體來說，是我在學習函數式編程的 Scheme 語言時，用函數編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在「模型的抽象程度」這一方面已經超出了NOIP的要求，所以暫且看不懂也沒關系。相信隨著你的OI之路逐漸延伸，有一天你會理解的。
我想說：「思考」是一個OIer最重要的品質。簡單的問題，深入思考以後，也能發現更多。
P09: 背包問題問法的變化
以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出演算法的。
例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之後得到。
還有，如果要求的是「總價值最小」「總件數最小」，只需簡單的將上面的狀態轉移方程中的max改成min即可。
Ⅵ 5.貪心演算法的核心思想。6.什麼是遞歸什麼是迭代兩者的區別，舉例說明。7.回溯的含義是什麼舉例
1、貪心演算法主要是把問題分成很多局部問題，用局部最優解合成整體最優解。因此使用這種演算法需要此問題滿足兩個條件，一個是能夠分成多個能夠求解的局部問題，第二個就是局部問題的解能夠合成最優解。和動態規劃、回溯等相比差別就是再不回溯的前提下找出整體最優解或者接近最優解，速度快但應用有比較大的限制。
2、迭代也叫遞推，通過重復執行某一步驟或者函數來求得計算結果
遞歸是指函數中直接或者間接調用自身
舉例：
求a乘以2的10次方等於幾
迭代：
for (i=0;i<10;i++)
a *= 2;
遞歸：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}
db(a,0);
3、回溯的含義就是在搜索問題的狀態過程中，如果不能繼續前進，再向後回到岔口，換一條路繼續搜索，直到搜索完所有狀態或者查找到需要的狀態。
舉例：（最典型的就是樹的深度搜索，下面舉一個簡單的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//從3開始查找1
int read[10]=(0);//是否查找過
int readNum = 0;//查找過的個數
int forward = 1;//1為左，2為右
int tmp = 0,index = 5;
tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}
if (index <=0 || index>=9)
forward = 3 - forward;
}
Ⅶ 大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系
對於，大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系這個問題，首先要來聊聊他們的聯系：1、都是一種推導演算法；2、將它們分解為子問題求解，它們都需要有最優子結構。這兩個特徵師門的聯系。
拓展資料：
貪婪演算法是指在解決問題時，它總是在當前做出最佳選擇。也就是說，在不考慮全局優化的情況下，該演算法在某種意義上獲得了局部最優解。貪婪演算法不能得到所有問題的全局最優解。關鍵是貪婪策略的選擇。
動態規劃是運籌學的一個分支，是解決決策過程優化的過程。20世紀50年代初，美國數學家R·貝爾曼等人在研究多階段決策過程的最優化問題時，提出了著名的最優化原理，建立了動態規劃。動態規劃在工程技術、經濟、工業生產、軍事和自動控制等領域有著廣泛的應用，在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題上都取得了顯著的成果。
Ⅷ 關於貪心演算法的應用范圍的問題
滿足最優子結構。做這些題最先肯定是要寫狀態轉移方程的，其實從狀態轉移方程上就可看出來，簡單的說就是把狀態轉移方程寫出來以後是類似這么個形式：s[i]=max{s[i-1]+c1,s[i-2]+c1,.....}+c2其中c1，c2為不隨各個具體狀態而變的常數。也就是說消去公共常數偏移（或者是*比例放縮）後這個max（min）函數是可以直接地一直寫到底，構成一個只有max（min，或兩者均有）的式子。而動態規劃的式子中的各個子狀態部分是要和一個非常值函數（這些函數的自變數與狀態或狀態的轉移方式有關）運算的，也就是說如果迭代地寫到底，會有大量函數（這些函數的自變數與狀態或狀態的轉移方式有關）存在。