背包问题是一个经典的动态规划问题,而贪心算法是一种常用的解决背包问题的方法,这篇文章主要给大家介绍了关于C语言背包问题求解(贪心方法)的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下
问题描述：
- 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
- 物品：A B C D E F G
- 重量：35 30 60 50 40 10 25
- 价值：10 40 30 50 35 40 30
算法描述：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
问题分析：
1.目标函数： ∑pi最大，使得装入背包中的所有物品pi的价值加起来最大。
2.约束条件：装入的物品总重量不超过背包容量：∑wi<=M( M=150)
3.贪心策略： 选择单位重量价值最大的物品
算法设计：
- 计算出每个物品单位重量的价值
- 按单位价值从大到小将物品排序
- 根据背包当前所剩容量选取物品
- 如果背包的容量大于当前物品的重量，那么就将当前物品装进去。否则，那么就将当前物品分割再装进去，然后跳出循环结束。
代码实现：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
float z[maxn];
void Sort(int n,float w[],float v[]){
for(int i=0;i<n;i++)
z[i]=v[i]/w[i];//用z[]存物品的单位重量价值
for(int i=0;i<n;i++){//此排序的策略是每次把单位重量物品的价值最大的物品放在前面
for(int j=i+1;j<n;j++){
if(z[i]<z[j]){
float temp = z[i];
z[i] = z[j];
z[j]=temp;
float tempw = w[i];
w[i] = w[j];
w[j] = tempw;
float tempv = v[i];
v[i] = v[j];
v[j] = tempv;
}
}
}
}
void fire(int n,float w[],float v[],float x[],float pimax){
Sort(n,w,v);//根据单位重量物品的价值对物品进行排序
int i;
for(i=0;i<n;i++){
if(w[i]>pimax) break;
x[i] = 1; //x[]数组用来记录此次是否选择物品，1代表全部拿走，0代表不拿，小数代表部分拿
pimax -= w[i];
}
if(i<=n-1) x[i] = pimax/w[i];
}
int main(){
int n;
float pi=0;
float pimax,v[maxn],w[maxn],x[maxn];//w[],每个物品的重量,v[]代表每个物品的价值,pimax代表最大容量
memset(x,0,sizeof(x));
cout<<"请输入最大容量：";
cin>>pimax;
cout<<"请输入物品(物品可以任意分割)数量：";
cin>>n;
cout<<"请输入每个物品的重量和价值："<<endl;
for(int i=0;i<n;i++){
cin>>w[i]>>v[i];
}
fire(n,w,v,x,pimax);
for(int i=0;i<n;i++){
if(x[i]==1){
pi+=v[i];
}
else{
pi+=v[i]*x[i];
}
}
cout<<"最终收获的物品(物品可以任意分割)价值为："<<pi<<endl;
return 0;
}
运行结果：
总结
到此这篇关于C语言背包问题求解(贪心方法)的文章就介绍到这了,更多相关C语言背包问题内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
最新评论