问题描述: 给定 n 种物品, 1 个背包, 背包容量为 c, 每个物品 i 的价值为 vi, 重量为 wi, 如何选择装入物品能使背包的总价值最大?
注意: 与 0-1 背包问题不同, 在选择物品 i 装入背包时, 可以选择物品 i 的一部分, 而不一定要全部装入背包, 1<=i<=n
形式化描述: 给定 c>0, wi>0, vi>0 , 1≤i≤n. 要求找一 n 元向量 A=(x1,x2,...,xn), 0<=xi<=1[0~1 表示取物品的某一部分] ,1<=i<=n, 使得 ∑ wixi≤c[物品的重量和小于背包总容量] 而且∑ vixi 达到最大.
算法思路: 将物品按照单位重量价值进行排序 (从大到小), 将尽可能多的单位重量价值最高的物品装入背包, 若将这种物品全部装入背包后, 背包还有多余容量, 则选择单位重量价值次高的并尽可能多地装入背包. 如果最后一件物品无法全部装入, 则计算可以装入的比例, 然后按比例装入.
代码实现:
数据结构: 结构体
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct item{
- int weight;// 物品的重量
- int value;// 物品的价值
- float bi;// 物品单位重量的价值
- float rate;// 使用率: 1 代表物品完整放入, 小于 1 代表被分割后放入
- }items[100];
- bool cmp(const item &a,const item &b){
- return a.bi>b.bi;
- }
- int main(){
- int n;//n 件物品
- float c;// 背包容量为 c
- cout<<"输入物品件数和背包容量:"<<endl;
- cin>>n>>c;
- cout<<"依次输入每件物品的价值和重量:"<<endl;
- float v[n],w[n];//v[n]:n 件物品的价值, w[n]:n 件商品的重量
- for(int i=0;i<n;i++){
- cin>>items[i].value>>items[i].weight;
- items[i].bi=items[i].value/items[i].weight;// 计算单位重量价值
- items[i].rate=0;// 初始化每件物品的使用率
- }
- sort(items,items+n,cmp);// 按照单位重量的价值排序
- int sum=0,j=0;
- for(j=0;j<n;j++){
- if(items[j].weight<=c){// 选择单位价值重量最大的并且不超过背包容量的
- items[j].rate=1;
- sum+=items[j].weight;
- c-=items[j].weight;
- cout<<"重:"<<items[j].weight<<", 价值:"<<items[j].value<<"的物品被放入了背包"<<endl<<"放入比例:"<<items[j].rate<<endl;
- }
- else break;
- }
- if(j<n){// 物品未装完
- items[j].rate=c/items[j].weight;// 背包容量还剩 c, 计算出未装入的物品能装多少的比例
- sum+=items[j].rate*items[j].weight;// 加上装入部分比例物品的重量
- cout<<"重:"<<items[j].weight<<", 价值:"<<items[j].value<<"被放入了背包"<<endl<<"放入比例:"<<items[j].rate<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2868672.html