贪心算法的讲解： 贪心算法 本题链接： P2240 【深基12.例1】部分背包问题
第一种：结构体解题 #include<bits/stdc++.h> using namespace std; struct node { double w;//重量 double v;//价值 double p;//均价 }a[101]; int N; double T,sum; bool cmp(node a, node b) { return a.p > b.p; } int main() { cin >> N >> T; for (int i = 0; i < N; i++) { cin >> a[i].w >> a[i].v; a[i].p = a[i].v / a[i].w; } sort(a, a + N, cmp); for (int i = 0; i <N; i++) { if(T-a[i].w>-0.00001) { T -= a[i].w; sum += a[i].v; } else { sum += T * a[i].p;//如果装不下就分割金币 break; } } printf("%.2lf", sum);//保留小数点后两位输出 return 0; }第二种：普通解题
#include<bits/stdc++.h> using namespace std; int N; double T,p[101],w[101], v[101],sum;//意义和上题解一样 int main() { cin >> N >> T; for (int i = 0; i < N; i++) { cin >> w[i] >> v[i]; p[i] = v[i] / w[i]; } for (int i = 0; i < N; i++) { for(int j = 0;j < N-1; j++) { if (n[j] > n[j + 1]) { swap(w[j], w[j + 1]); swap(v[j], v[j + 1]); swap(p[j], p[j + 1]); } } } for(int i=N-1;i>=0;i--) { if (T - w[i]> -0.000001) { T -= w[i]; sum += v[i]; } else { sum += T * p[i]; break; } } printf("%.2lf", sum); return 0; }核心代码：主要思想在于对金币的分割
for (int i = 0; i <N; i++) { if(T-a[i].w>-0.00001) { T -= a[i].w; sum += a[i].v; } else { sum += T * a[i].p;//如果装不下就分割金币 break; } }本题主要考察两个知识点：排序和贪心算法
