Partition函数的具体实现 template
int Partition (Type a[], int p, int r) {
int i = p, j = r + 1; Type x=a[p];
// 将< x的元素交换到左边区域 // 将> x的元素交换到右边区域 while (true) {
while (a[++i]
3. 用贪心算法求解最优装载问题。 最优装载问题 P95 课件第4章(2)第3-8页
template
void Loading(int x[], Type w[], Type c, int n) {
int *t = new int [n+1]; Sort(w, t, n);
for (int i = 1; i <= n; i++) x[i] = 0; for (int j = 1; j <= n && w[t[j]] <= c; j++) {x[t[i]] = 1; c -= w[t[j]];} }
4. 用回溯法求解0-1背包/批处理作业调度 /最大团问题，要会画解空间树。 例1：用回溯法求解0-1背包 P133课件第5章(2)第24-38页 template
private:
Typep Bound(int i); //计算上界 void Backtrack(int i); Typew c; //背包容量 int n; //物品数
Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最优价值 };
void Knap
if(Bound(i+1)>bestp) //进入右子树 Backtrack(i+1); }
Typep Knap
Typew cleft=c-cw; //剩余的背包容量 Typep b=cp; //b为当前价值 //依次装入单位重量价值高的整个物品
while(i<=n&&w[i]<=cleft)
{ cleft-=w[i]; b+=p[i]; i++; } if(i<=n) //装入物品的一部分 b+=p[i]*cleft/w[i]; return b; //返回上界 }
class Object //物品类 {
friend int Knapsack(int *,int *,int,int); public:
int operator <(Object a) const {
return (d>=a.d); }
int ID; //物品编号 float d; //单位重量价值 };
Typep Knapsack( Typep p[],Typew w[],Typew c,int n) { //为Typep Knapsack初始化 Typew W=0; //总重量 Typep P=0; //总价值
Object* Q=new Object[n]; //创建物品数组，下标从0开始 for(int i=1;i<=n;i++) //初始物品数组数据 { Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; }
if(W<=c) //能装入所有物品 return P;
if(W<=c) //能装入所有物品 return P;
QuickSort(Q,0,n-1); //依物品单位重量价值非增排序
Knap
{ K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; K.Backtrack(1); delete[] Q; delete[] K.w; delete[] K.p; return K.bestp; }
例2：批处理作业调度 课件第5章(2)P2-5问题描述,课本P125-127 解空间：排列树 算法描述： class Flowshop {
static int [][] m, // 各作业所需的处理时间 [] x, // 当前作业调度 [] bestx, // 当前最优作业调度
[] f2, // 机器2完成处理时间 f1, // 机器1完成处理时间 f, // 完成时间和
bestf, // 当前最优的完成时间和 n; // 作业数 static void Backtrack(int i) {
if (i > n)
{ for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; } else
for (int j = i; j <= n; j++) {
f1+=m[x[j]][1];//第j个作业在第一台机器上所需时间 f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2]; f+=f2[i];
if (f < bestf) //约束函数
{ Swap(x[i], x[j]); Backtrack(i+1); Swap(x[i], x[j]); f1 - =m[x[j]][1]; f - =f2[i]; } }
}