【算法分析】 最优策略：每一次贪心地选当前单位重量价值最大的金属装入口袋。 【参考代码】 【时间复杂度】 O(kslog⁡2s)O(ks\log_{2}s)O(kslog2 s) 【预计得分】 100pts100pts100pts

#include<iostream> #include<algorithm> //倒库 #include<iomanip> using namespace std; const int N=1e5+5; int t; //表次数的变量 struct Node{ //结构体 int m,v; //m表质量，v表价值 double s; //s是他俩的比值，为sort准备的 }a[N]; bool cmp(Node a,Node b){ //比较函数 return a.s>b.s; } int main(){ cin>>t; //输入次数 while(t--){ //整体循环 int w,n; //定义w用于袋子容量，n作为金属数量 double sum=0; //sum是最后的ans cin>>w>>n; for(int i=1;i<=n;i++){ cin>>a[i].m>>a[i].v; a[i].s=a[i].v1.0/a[i].m;//输入每个金属的质量和价值的同时计算单个的价值 } sort(a+1,a+n+1,cmp);//根据单价排序 for(int i=1;i<=n;i++){ //根据排序后的结果计算ans if(w==0) break; //退出 if(w<a[i].m){ //如果w不能容纳 sum+=wa[i].s; //由于金属可以随意切割，将w剩下的容量装满 w=0; //清空容量（退出循环） }else{ //如果w还够容纳当前金属的全部 sum+=a[i].v; //直接加上价值 w-=a[i].m; //w容量自动减少 } } cout<<fixed<<setprecision(2)<<sum<<endl; //保留两位小数的输出 } return 0; }

#include<bits/stdc++.h> using namespace std; const int N=100001; struct stu{ double w,v,wv; }a[N]; bool cmp(stu aa,stu bb) { return aa.wv>bb.wv; } int main() { int k; cin>>k; while(k--) { int n,m; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>a[i].w>>a[i].v; a[i].wv=a[i].v/a[i].w; } sort(a+1,a+1+n,cmp); double sum=0; for(int i=1;i<=n;++i) { if(m>=a[i].w) sum+=a[i].v; }

先建一个列表，存储价值/数量，排好序（连着另外两个一起排好），然后一直遍历，直到当前金属没法放下，不要去存另外的金属，把当前金属切割带走，break掉

#include<bits/stdc++.h> using namespace std; struct node{ double num; double v; double d; }; bool cmp(node a , node b){ return a.d<b.d; } int main(){ int n; cin>>n; while(n--){ long long w,s; cin>>w; cin>>s; node a[s]; for(int i=0;i<s;i++){ cin>>a[i].num>>a[i].v; a[i].d=a[i].num/a[i].v; } sort(a,a+s,cmp); double cnt=0; for(int i=0;i<s;i++){ if(a[i].num<=w){ w-=a[i].num; cnt+=a[i].v; } else{ cnt+=w/a[i].d; break; } } printf("%.2f",cnt); cout<<endl; } return 0; }

#include <iostream> #include <algorithm> using namespace std; struct node{ int v,n; double up; }; bool cmp(node x,node y){ return x.up>y.up; } int main(){ int k; cin>>k; while (k--){ int w,s; cin>>w>>s; node a[105]; double va=0; for(int i=1;i<=s;i++){ cin>>a[i].n>>a[i].v; a[i].up = a[i].v1.0/a[i].n; } sort(a+1,a****,cmp); for(int i=1;i<=s;i++){ if(w<a[i].n){ va+=a[i].upw; break; } va+=a[i].v; w-=a[i].n; } printf("%.2f\n",va); } return 0; }

#include<bits/stdc++.h> using namespace std; int k,w,s; struct P{ int n,va; double v; }p[100005]; bool cmp(P a,P b){ return a.v>b.v; } int main(){ cin>>k; for(int i=1;i<=k;i++){ double sum=0; cin>>w>>s; for(int i=1;i<=s;i++){ cin>>p[i].n>>p[i].va; p[i].v=(1.0)p[i].va/p[i].n; } sort(p+1,p+1+s,cmp); for(int i=1;i<=s;i++){ if(w>=p[i].n){ sum+=p[i].va; w-=p[i].n; }else{ sum+=wp[i].v; break; } } printf("%.2lf\n",sum); } return 0; }