问题描述

acm水题求解，关于贪心算法

#include
#include
#include
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop /
????
int main(int argc, char* argv) {
???? int M,N;
???? while(cin>>M>>N)
???? {
????????? if(M==-1 && N==-1)
????????? break;
????????? {???? double j[1001];
?????????????? double f[1001];
?????????????? double x[1001];
?????????????? for(int i=0; i
?????????????? {
??????????????????? cin>>j[i];
??????????????????? cin>>f[i];
???????????????????????????????????????
?????????????? }
?????????????? for(int k=0; k<N; k++)??? //性价比
?????????????? {
??????????????????? x[k] = j[k] / f[k];
?????????????? }
??????????????
?????????????? for(int i=0; i<N; i++)?? //性价比排序
?????????????? {
??????????????????? for(int k=i+1; k<N; k++)
??????????????????? {
???????????????????????? if(x[i]<x[k])
???????????????????????? {
????????????????????????????? double temp = x[i];
????????????????????????????? x[i] = x[k];
????????????????????????????? x[k] = temp;
????????????????????????????? temp = j[i];
????????????????????????????? j[i] = j[k];
????????????????????????????? j[k] = temp;
????????????????????????????? temp = f[i];
????????????????????????????? f[i] = f[k];
????????????????????????????? f[k] = temp;
?????????????????????????????
???????????????????????? }
????????????????????????
??????????????????? }
???????????????????
?????????????? }
??????????????
??????????????
?????????????? double sum = 0;
?????????????? for(int i=0; i<N; i++)
?????????????? {
??????????????????? if(M==0)
??????????????????? break;
???????????????????
??????????????????? for(int k=0; k<f[i]; k++)
??????????????????? {
???????????????????????? if(M==0)
???????????????????????? break;
???????????????????????? sum = sum + x[i];
???????????????????????? M--;?????????????????????????????????????????????????????????????????????
??????????????????? }
?????????????? }
??????????????
?????????????? ?
?????????????? cout<<setiosflags(ios::fixed)<<setprecision(3)<<sum<<endl;
??????????????
????????? }
?????????
???? }
????
???? return 0;
}

????

解决方案

给的Wa，不知道该怎么测试。还不会其他高级的知识呢。

解决方案二：

acm-背包问题(贪心算法)

解决方案三：

解决方案四：

解释下题意吧……手机上看图太费劲拉