問題敘述：如下圖表示活動的開始和結束時間，s[i],開始時間；f[j]結束時間。現在要進行一些列如下活動，注意每個時間段只能進行一場活動，也就是活動不能同時進行，要求舉行的活動次數最多。求調度方法。
老規矩，動態規劃，要找出兩個問題：
1，子問題的最優解；
2，子問題是什麼。
abviously,本問題的最優解為：活動數的次數最多，子問題是：看遞推公式
設c[i]為第i個 位置處的活動次數.......做不出來了，以後補充。
本想用動態規劃試試做做，操蛋的做不出來，算了還是貪心吧，畢竟貪心最簡單對於活動調度，不過有個證明過程。先上代碼吧。
[cpp]
#include<iostream>
using namespace std;
//s 活動開始時間的數組，f活動結束時間的數組，n 數組的大小；
const int N=11;
void GreedySelector(int* s,int* f,int n )
{
bool A[N];
A[0]=true;
int j=0;
for(int i=1;i<N;++i)
{
if(s[i]>f[j])
{
A[i]=true;
j=i;
}
else
{
A[i]=false;
}
}
for(int k=0;k<N;++k)
{
if(A[k]==true)
cout<<k<<" ";
}
}
int main()
{
int s[N]={1,3,0,5,3,5,6,8,8,2,12};//活動的開始時間
int f[N]={4,5,6,7,8,9,10,11,12,13,14};//活動的結束時間
GreedySelector( s, f, N );
return 0;
}
#include<iostream>
using namespace std;
//s 活動開始時間的數組，f活動結束時間的數組，n 數組的大小；
const int N=11;
void GreedySelector(int* s,int* f,int n )
{
bool A[N];
A[0]=true;
int j=0;
for(int i=1;i<N;++i)
{
if(s[i]>f[j])
{
A[i]=true;
j=i;
}
else
{
A[i]=false;
}
}
for(int k=0;k<N;++k)
{
if(A[k]==true)
cout<<k<<" ";
}
}
int main()
{
int s[N]={1,3,0,5,3,5,6,8,8,2,12};//活動的開始時間
int f[N]={4,5,6,7,8,9,10,11,12,13,14};//活動的結束時間
GreedySelector( s, f, N );
return 0;
}
測試結果：
證明略，沒怎麼明白，智商啊，亵渎了 我的大腦袋。
把算法導論的證明貼出來吧：
再來做個例子吧：
背包問題：
0-1背包問題：有一個竊賊在一家商店時發現有n件物品，第i件物品值vi元，重wi磅。此處，vi,wi都是整數，。他希望帶走的東西越值錢越好，但他的背包中至多只能裝下W磅。
，W為一整數。應該帶走那幾樣東西呢？（0-1的意思是：物品或被帶走，或被留下，不能帶走一部分，留下一部分）
部分背包問題：場景與上面類似，但是竊賊可以帶走物品的一部分，而不必做出0-1的二分選擇。
下面一個個來解決吧。
0-1：
我自己參照寫的代碼：
[cpp]
#include<iostream>
using namespace std;
//w 物品的重量，v物品的價值，count物品的數量，m是背包最大的容量
void processing(int* w,int* v,int count,int m,int(* c)[11])
{
for(int i=1;i<=count;++i)
for(int j=1;j<=m;++j)
{
if(w[i]<=j)//可以放對應的背包了
{
if(c[i-1][j]>c[i-1][j-w[i]]+v[i])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i-1][j-w[i]]+v[i];
}
else
{
c[i][j]=c[i-1][j];
}
}
}
void Printf(int count,int m,int (*c)[11],int* log,int *w)
{
int j=m;
for(int i=count;i>=1;--i)
if(c[i][j]==c[i-1][j])
log[i]=0;
else
{
log[i]=1;
j=j-w[i];
}
}
int main()
{
int w[4]={0,3,4,5};
int v[4]={0,4,5,6};
int c[4][11];
int log[4];
int count=3;
int m=10;
for(int i=0;i<=3;++i)
for(int j=0;j<=10;++j)
c[i][j]=0;
processing(w, v,3,10,c);
Printf(3,10,c,log,w);
cout<<"裝入的物品為：";
for(int i=1;i<=count;++i)
if(log[i]==1)cout<<i<<" ";
cout<<"總價值為："<<c[count][m];
}
#include<iostream>
using namespace std;
//w 物品的重量，v物品的價值，count物品的數量，m是背包最大的容量
void processing(int* w,int* v,int count,int m,int(* c)[11])
{
for(int i=1;i<=count;++i)
for(int j=1;j<=m;++j)
{
if(w[i]<=j)//可以放對應的背包了
{
if(c[i-1][j]>c[i-1][j-w[i]]+v[i])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i-1][j-w[i]]+v[i];
}
else
{
c[i][j]=c[i-1][j];
}
}
}
void Printf(int count,int m,int (*c)[11],int* log,int *w)
{
int j=m;
for(int i=count;i>=1;--i)
if(c[i][j]==c[i-1][j])
log[i]=0;
else
{
log[i]=1;
j=j-w[i];
}
}
int main()
{
int w[4]={0,3,4,5};
int v[4]={0,4,5,6};
int c[4][11];
int log[4];
int count=3;
int m=10;
for(int i=0;i<=3;++i)
for(int j=0;j<=10;++j)
c[i][j]=0;
processing(w, v,3,10,c);
Printf(3,10,c,log,w);
cout<<"裝入的物品為：";
for(int i=1;i<=count;++i)
if(log[i]==1)cout<<i<<" ";
cout<<"總價值為："<<c[count][m];
}
部分背包問題：
上代碼
[cpp]
#include<iostream>
using namespace std;
const int n=10;
//定義一個結構體
typedef struct goods
{
int w;//物品的重量
int v;//物品的價值
double VbyW;
} goods;
struct selectedGood
{
int num;//選擇的商品號
int residue;//最後一種商品被選擇的數量，因為部分選取
};
void fastSort(goods * inputData,int n,int startLoc);
void backBag(goods* igoods,int n,int m,selectedGood* SG);
int main()
{
int W[n]={12,3,5,6,3,43,56,2,65,43};
int V[n]={4,1,7,4,65,32,4,8,3,7};
int m=30;
selectedGood SG;
//初始化
SG.num=-1;
SG.residue=0;
selectedGood* pSG=&SG;
goods igoods[n];
for(int i=0;i<n;++i)
igoods[i].w=W[i];
for(int j=0;j<n;++j)
igoods[j].v=V[j];
for(int k=0;k<n;++k)
igoods[k].VbyW=(double)igoods[k].v/igoods[k].w;
fastSort(igoods,n,0);//對單位重量的價值進行排序
backBag( igoods, n, m,pSG);
cout<<"放入背包的物品："<<endl;
int k;
for( k=0;k<pSG->num;++k)
{
cout<<igoods[k].w<<" ";
}
if(pSG->residue!=0)
cout<<"最後一個物品"<< igoods[pSG->num-1].w<<"只取"<< pSG->residue;
return 0;
}
void backBag(goods* igoods,int n,int m,selectedGood* SG)
{
int tmp=0;
int residue=0;
int i;
for( i=0;i<n;++i)
{
//tmp+=igoods[i].w;
if(tmp+igoods[i].w<=m)
{
tmp+=igoods[i].w;
}
else
{
SG->residue=m-tmp;
SG->num=i+1;
break;
}
}
if(i==n)
{
SG->num=i+1;
}
}
void fastSort(goods * inputData,int n,int startLoc)
{
if(n<2) return ;//遞歸停止的條件
int i=startLoc-1;//指向最後一個小於基元的數據
int j=startLoc;//移動j，挨個遍歷元素
double baseDa=inputData[startLoc+n-1].VbyW;//獲取基元
goods tmp;
int k=0;
while(j<=startLoc+n-1)
{
if(inputData[j].VbyW>inputData[startLoc+n-1].VbyW||j==startLoc+n-1)
{
i++;
k++;
//交換
tmp=inputData[j];
inputData[j]=inputData[i];
inputData[i]=tmp;
}
j++;
}
startLoc=i-k+1;//左邊分組的位置，右邊分組的位置為：i+1
fastSort(inputData,i-startLoc,startLoc);
fastSort(inputData,n-(i-startLoc)-1,i+1);
}
#include<iostream>
using namespace std;
const int n=10;
//定義一個結構體
typedef struct goods
{
int w;//物品的重量
int v;//物品的價值
double VbyW;
} goods;
struct selectedGood
{
int num;//選擇的商品號
int residue;//最後一種商品被選擇的數量，因為部分選取
};
void fastSort(goods * inputData,int n,int startLoc);
void backBag(goods* igoods,int n,int m,selectedGood* SG);
int main()
{
int W[n]={12,3,5,6,3,43,56,2,65,43};
int V[n]={4,1,7,4,65,32,4,8,3,7};
int m=30;
selectedGood SG;
//初始化
SG.num=-1;
SG.residue=0;
selectedGood* pSG=&SG;
goods igoods[n];
for(int i=0;i<n;++i)
igoods[i].w=W[i];
for(int j=0;j<n;++j)
igoods[j].v=V[j];
for(int k=0;k<n;++k)
igoods[k].VbyW=(double)igoods[k].v/igoods[k].w;
fastSort(igoods,n,0);//對單位重量的價值進行排序
backBag( igoods, n, m,pSG);
cout<<"放入背包的物品："<<endl;
int k;
for( k=0;k<pSG->num;++k)
{
cout<<igoods[k].w<<" ";
}
if(pSG->residue!=0)
cout<<"最後一個物品"<< igoods[pSG->num-1].w<<"只取"<< pSG->residue;
return 0;
}
void backBag(goods* igoods,int n,int m,selectedGood* SG)
{
int tmp=0;
int residue=0;
int i;
for( i=0;i<n;++i)
{
//tmp+=igoods[i].w;
if(tmp+igoods[i].w<=m)
{
tmp+=igoods[i].w;
}
else
{
SG->residue=m-tmp;
SG->num=i+1;
break;
}
}
if(i==n)
{
SG->num=i+1;
}
}
void fastSort(goods * inputData,int n,int startLoc)
{
if(n<2) return ;//遞歸停止的條件
int i=startLoc-1;//指向最後一個小於基元的數據
int j=startLoc;//移動j，挨個遍歷元素
double baseDa=inputData[startLoc+n-1].VbyW;//獲取基元
goods tmp;
int k=0;
while(j<=startLoc+n-1)
{
if(inputData[j].VbyW>inputData[startLoc+n-1].VbyW||j==startLoc+n-1)
{
i++;
k++;
//交換
tmp=inputData[j];
inputData[j]=inputData[i];
inputData[i]=tmp;
}
j++;
}
startLoc=i-k+1;//左邊分組的位置，右邊分組的位置為：i+1
fastSort(inputData,i-startLoc,startLoc);
fastSort(inputData,n-(i-startLoc)-1,i+1);
}
測試：
