4047 - 部分背包
一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是wi，它们的价值分别是vi元/公斤，求旅行者能获得最大总价值。
Input
第1行：两个整数，M背包容量（M<=1000）和N物品数量（N<=30）；
第2至N+1行：每行两个整数wi,vi,表示每个物品的重量和价值。
Output
一个数，表示最大总价值。
Examples
Input
100 3 40 2 50 3 70 3
Output
300
Solution C++
#include<iostream> #include<algorithm> using namespace std; const int N = 1005; struct food{ int w,v; }; food a[N]; bool comp(food x,food y){ return x.v>y.v; } int main(){ int M,n,ans=0; cin>>M>>n; for (int i=1; i<=n; i++) cin>>a[i].w>>a[i].v; sort(a+1,a+n+1,comp); for (int i=1; i<=n&&M>0; i++) if (M>=a[i].w) ans+=a[i].v*a[i].w,M-=a[i].w; else ans+=a[i].v*M,M=0; cout<<ans<<endl; return 0; }