一、问题如下：
给出n个大小为s1, s2,... , sn，价值为v1 ,v2,...,vn的物品，并设背包容量为C。
试设计一个贪心算法，找到非负实数x1,x2,…xn使和
编辑(从1到n求和)，在约束
编辑（从1到n求和）<=C下最大。
二、算法思想：
求解思路：
1、先求出各个物品的价值与体积的比value_v（注意浮点数强制类型转换，代码31行）
2、依据value_v排序。
3、优先存入此值大的物品。
4、若剩余空间不足存入整个物品，则按剩余空间存入部分即可。
（即此题与01背包问题区别是物品可拆分存入）
三、代码如下：
#include <bits/stdc++.h> using namespace std; #define N 1000 int n;//物品个数 int Bag=0;//背包容量 typedef struct ss{//定义物品结构体ss int v; int value; float value_v; }ss; ss s[N]; void InputV(int n){//输入各物品体积 for(int i=0;i<n;i++){ cin>>s[i].v; } } void InputValue(int n){//输入各物品价值 for(int i=0;i<n;i++){ cin>>s[i].value; } } void Setvalue_v(int n){//计算并存储各物品价值比 for(int i=0;i<n;i++){ s[i].value_v=(float)s[i].value/s[i].v;//注意此处float强制类型转化 } } bool cmp(ss s1,ss s2){//以递减 return s1.value_v > s2.value_v; } int main(){ cin>>n;//输入物品个数 cin>>Bag;//输入背包容量 InputValue(n);//输入各物品价值 InputV(n);//输入各物品体积 Setvalue_v(n);//计算各物品价值比 sort(s,s+n,cmp);//按物品价值比递减排序 int Sum=Bag;//Sum存储背包剩余容量 float SumValue=0;//记录能存入背包的最大价值 for(int i=0;i<n;i++){ if(Sum==0) break;//背包已装满，退出 else if(Sum>=s[i].v){//装入整个体积的物品i SumValue=SumValue+s[i].value;//将第i物品放入背包 Sum=Sum-s[i].v;//背包空间变小 } else if(Sum<s[i].v){//装入部分体积的物品i SumValue=SumValue+(float)Sum*s[i].value/s[i].v; Sum=0; } } if(SumValue!=0) cout<<SumValue<<endl; else cout<<" "; return 0; }
四、示例
1、示例输入：
3 20 25 24 15 18 15 10
2、示例输出
31.5
