贪心算法解决背包问题
贪心算法解决背包问题问题描述:给定 n 个物品和一个容量为 C 的背包,请给出物品装入背包的方案,使得背包中物品的总价值 M 最大,并满足:1.每个物品 I 的重量为 wi,价值为 vi。2.每个物品可拆分,背包中物品的总重量不能超过容量 C 。实验要求:程序要求:1)先写排序算法 Rank(),本文中使用快速排序完成,再写贪心算法 Greedy()。2)两个步骤需要单独定义在程...
贪心算法解决背包问题
问题描述:
给定 n 个物品和一个容量为 C 的背包,请给出物品装入背包的方案,使得背包中物品的总价值 M 最大,并满足:
1.每个物品 I 的重量为 wi,价值为 vi。
2.每个物品可拆分,背包中物品的总重量不能超过容量 C 。
实验要求:
程序要求:
1)先写排序算法 Rank(),本文中使用快速排序完成,再写贪心算法 Greedy()。
2)两个步骤需要单独定义在程序里,不写在主函数里。
贪心算法解背包问题的基本步骤:
1)计算每种物品单位重量的价值 Vi / Wi
2)依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
3)若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
4)依此策略一直进行下去,直到背包装满为止。
代码实现:
快速排序:
快速排序的实现主要部分是partition部分,partition是对数组针对某一个数(此处以 数组第一个元素为基础)来分区。注意参数列表中,index是设定的记录交换的数据,即在数组中数据交换位置的时候,用index数组来记录交换信息,等后续用index数组可以遍历到交换完位置的数据。
int Partition(double arr[],int index [], int left,int right){
int i=left, j=right;
double x = arr[left];
while(i!=j){
while(arr[j]>=x&&i<j) j--;
while(arr[i]<=x&&i<j) i++;
if(i>=j) break;
swap(arr[i],arr[j]);
swap(index[i],index[j]);
}
swap(arr[left],arr[i]);
swap(index[left],index[i]);
return i;
}
void rank(double arr[],int index[],int left,int right){
if(left<right){
int q=Partition(arr,index,left,right);
rank(arr,index,left,q-1);
rank(arr,index,q+1,right);
}
else return ;
}
贪心算法:
贪心算法的核心逻辑为每次都进行最优的选择。在此处注意处理当背包恰好可以放下一个物品时,最好的逻辑选择是不进入做除法的操作,在for循环内部实现。
void Greedy(int n, double c, double w[], int b[], double x[]){
int i;
for(i=n-1;i>=0;i--){
if(w[b[i]-1]>c) break;
x[b[i]-1]=1;
c-=w[b[i]-1];
}
if(i>=-1&&c>0) x[b[i]-1]=c/w[b[i]-1];
}
main函数测试:
运行前需要创建文件input.txt,写入读取的数据,同时创建output.txt文件,存放输出结果。
int main(){
ifstream input("input.txt");//打开输入文件
if(!input)cout<<"The file can not open!!"<<endl;//文件打开失败
int n=0;
double c;
input>>c;//读入背包容量
double index[100],w[100],v[100];//定义索引数组,物品质量数组,物品价值数组
while(!input.eof())
{
input>>index[n]>>w[n]>>v[n];//按照顺序一次读取ID,物品价值,物品质量
n++;
}
double totalvalue;
double a[n],x[n];
int b[n];
for(int i=0;i<n;i++)x[i]=0;
for(int i =0;i<n;i++){
a[i]=v[i]/w[i];
b[i]=i+1;
}
rank(a,b,0,n-1);
Greedy(n,c,w,b,x);
cout<<"The result is in the output.txt!"<<endl;
ofstream output;
output.open("output.txt");
if(!output)cout<<"The file can not be open!!"<<endl;
for(int i=0;i<n;i++)
{
totalvalue+=v[i]*x[i];
}
output<<totalvalue<<endl;
for(int i=0;i<n;i++)
{
output<<i+1<<"\t"<<x[i]*w[i]<<"\t"<<v[i]*x[i]<<"\t";
output<<endl;
}
}
运行结果
实验总结:
贪心算法可以解决背包问题,而不能解决0-1背包问题。贪心算法的核心思想是每次都做最优选择,因此在进行贪心算法的时候,首先需要考虑数据按照什么标准排序,贪心的选择按照排序进行,每次选择最优结果,选择后,问题规模下降。因此,贪心算法是自顶向下的算法。
更多推荐
所有评论(0)