《实用算法的分析与程序设计》的读书笔记（第1天）
由于很多网友的推荐，终于使我静下心来好好的看一下《实用算法的分析与程序设计》这本书！果然是名付其实！现在将我看书过程中遇到的题目用c++给出，原文是用pascal给出的！很多朋友甚至因为这个原因而放弃这本书！很可惜！注：这些程序我都在bc5。0中通过了！
递推 第4页
一辆重型卡车欲穿过1删公里的沙漠，卡车耗油为1升／公里，卡车总裁油能力为500
公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，
使卡车能顺利穿越沙漠，试问司机如何建立这些贮油点?每一贮泊点应存多少汽油，才能
使卡车以消耗最少汽油的代价通过沙漠?
题解：
#include<iostream.h>
#include<iomanip.h>
void oil_lib()
{
int k;float d,dl;
float oil[10],dis[10];
cout<<"No."<<setw(20)<<" distance(k.m)"<<setw(90)<<" oil(l.)"<<endl;
k=1;
d=500;
dis[1]=500;
oil[1]=500;
do{
k++;
d+=500/(2*k-1);
dis[k]=d;
oil[k]=oil[k-1]+500;
}while(d<1000);
dis[k]=1000;
dl=1000-dis[k-1];
oil[k]=dl*(2*k+1)+oil[k-1];
for(int i=0;i<k;i++)
cout<<i<<setw(20)<<(1000-dis[k-i])<<setw(90)<<oil[k-i]<<endl;
}
贪心法 第10页
有一个贼在偷窃一家商店时发现有N件物品：第i件物品值Vi元，重Wi磅，(1<=i
＜=n)， 此处Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能
装下W磅的东西(W为整数)。
如果允许小偷可带走某个物品的一部分，小偷应该带走哪几件东西， 每件东西
的重量是多少?
题解：
#include<iostream.h>
#include<stdio.h>
const maxn=1000;
class Node{
public:
Node(){}
Node(int a,float b,float c):num(a),w(b),v(c){vper=c/w;}
int num; float w,v,vper;
};
Node list[maxn],lt[maxn];
void print(int n)
{
for(int i=0;i<n;i++)
cout<<list[i].num<<" "<<list[i].w<<" "<<list[i].v<<endl;
cout<<endl;
}
void merge(int p,int q,int r)
{
int i,j,t;
t=p;i=p;j=q+1;
while(t<=r){
if( (i<=q)&&((j>r)||(list[i].vper>=list[j].vper)) ){
lt[t]=list[i]; i++;
}else{ lt[t]=list[j]; j++; }
t++;
}
for(int s=p;s<=r;s++)
list[s]=lt[s];
}
void merge_sort(int p,int r)
{
int q;
if(p!=r){
q=(p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}
void Partial_Bag_Problem(int N,float W)
{
float V=0;
float w,v;
for(int i=0;i<N;i++){ /*物品的重量和价值*/
cin>>w>>v;
Node node((i+1),w,v);
list[i]=node;
}
/*print(N)*/
merge_sort(0,N-1);
/*print(N)*/
int j=0;
while(W>list[j].w&&j<N){
W-=list[j].w;
V+=list[j].v;
printf("%d%8.2f%8.2f\n",list[j].num,list[j].w,list[j].v);
j++;
}
if(j<N&&W!=0){
V+=W*list[j].vper;
printf("%d%8.2f%8.2f\n",list[j].num,W,W*list[j].vper);
W=0;
}
cout<<"total value: "<<V<<endl;
}
int main()
{
int N,W;
cin>>N>>W;
Partial_Bag_Problem(N,W);
return 1;
}
贪心法 第15页
任务调度问题
一个单位时间任务是个作业，如要在计算机上运行一个程序，它恰覆盖一个单位的
运行时间。给定一个单位时间任务的集合S，对S的一个调度即S的一个排列，其中规定了
这些任务的执行顺序。该调度中的第一个任务开始于时间0，结束于时间15第二个任务开始
于时间1，结束于时间2；……。
单处理器上具有期限和罚款的单位时间任务调度问题的输人如下：
1．包含n个单位时间任务的集合S＝f1，2，……，n75
2．n个取整的期限d1，I。．…，d n，(1＜d5之n)，任务i要求在di前完成；
3．21个非负的权(或罚款)w：，·，b…，wno如果任务i没在时间di之前结束
罚款w5；．
要求找出S的一个调度，使之最小化总的罚款。
题解：
#include<iostream.h>
const maxn=500;
class Node{
public:
Node(){}
Node(int a,int b,int c):k(a),d(b),w(c){}
int k,d,w;
};
Node list[maxn],lt[maxn];
void print(int n)
{
for(int i=0;i<n;i++)
cout<<list[i].k<<" "<<list[i].d<<" "<<list[i].w<<endl;
cout<<endl;
}
void merge(int p,int q,int r)
{
int i,j,t;
t=p,i=p,j=q+1;
while(t<=r){
if((i<=q)&&((j>r)||(list[i].w>=list[j].w)))
lt[t]=list[i++];
else lt[t]=list[j++];
t++;
}
for(int s=p;s<=r;s++)
list[s]=lt[s];
}
void merge_sort(int p,int r)
{
int q;
if(p!=r){
q=(p+r-1)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}
void Tasks_with_limit_and_fine(int N)
{
int d,w;
int pck[maxn];
int num=0,t,sum=0; /*当前完成的任务个数 罚款总数*/
for(int i=0;i<N;i++){
cin>>d>>w;
Node node((i+1),d,w);
list[i]=node;
}
/*print(N);*/
merge_sort(0,N-1);
/*print(N);*/
int i,j;
for(i=0;i<N;i++){
t=0;
for(j=0;j<num;j++)
if(list[pck[j]].d<=num)
t++;
/* cout<<"t:"<<t<<" ";*/
if(t<list[i].d){
pck[num]=i; list[i].k=-list[i].k; j=num++; /*cout<<"j:"<<j<<" ";*/
while(j>0){
if(list[pck[j]].d<list[pck[j-1]].d){
t=pck[j];pck[j]=pck[j-1];pck[j-1]=t;
}
j--;
}
}
}
for(i=0;i<num;i++)
cout<<(-list[pck[i]].k)<<" ";
cout<<endl;
for(i=0;i<N;i++)
if(list[i].k>0){
cout<<list[i].k<<" ";
sum+=list[i].w;
}
cout<<endl;
cout<<"total fine= "<<sum<<endl;
}
int main()
{
int N;
cin>>N;
Tasks_with_limit_and_fine(N);
return 1;
}
