1.P2240 【深基12.例1】部分背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
算性价比，进行排序来进行局部最优解
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int t,n; 5 6 struct node 7 { 8 double w,v,p; 9 }a[110]; 10 11 bool cmp(node a,node b) 12 { 13 return a.p > b.p ; 14 } 15 16 int main() 17 { 18 cin >> n >> t; 19 20 for (int i = 1; i <= n; i ++ ) 21 { 22 cin >> a[i].w >> a[i].v; 23 a[i].p = a[i].v / a[i].w; 24 } 25 26 sort(a + 1,a + 1 + n,cmp); 27 28 double sum = 0; 29 for (int i = 1; i <= n; i ++ ) 30 { 31 if(t >= a[i].w) 32 { 33 t -=a[i].w; 34 sum +=a[i].v; 35 } 36 37 else 38 { 39 sum +=a[i].p * (t); 40 break; 41 } 42 } 43 printf("%.2f\n",sum); 44 }