背包问题（背包可划分）贪心算法

#include<iostream> #include<string> #include<memory.h> #include<cstdio> #include<string> #include <algorithm> #define NUM 1001 using namespace std; int charaNum[NUM] ;//存放输入数据的数组 int tempArr[NUM]; struct bag { int w;//体积 int v;//价值 double x;//装入背包的量 double c;//性价比 int index;//编号 }a[NUM]; bool cmp(const bag & a, const bag & b) { return a.c>=b.c? true: false; } double greedySelect(bag * A,int num,int c) { double sum = 0; int i = 0; double cleft = c; while(i<num && a[i].w<=cleft) { cleft-=a[i].w; sum+=a[i].v; a[a[i].index].x=1.0; i++; } if(i<num) { a[a[i].index].x = 1.0*cleft/a[i].w; sum+=1.0*a[i].v*cleft/a[i].w; } return sum; } int main() { freopen("in.txt","r",stdin); int num; while(cin>>num && num != 0) { for(int i = 0;i<num;i++) { cin>>a[i].w>>a[i].v; a[i].c = a[i].v*1.0/a[i].w; a[i].index = i; } sort(a,a+num,cmp); cout<<greedySelect(a,num,50)<<endl; for(int i = 0;i<num;i++) { cout<<a[i].x<<" "; } } }

输入：

3 20 100 30 120 10 60 0

输出：

240 1 0.666667 1