问题：给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 wi ，价值vi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。
#include <iostream> #include<vector> #include<algorithm> using namespace std; struct bag{ int w; //物品的重量 int v; //物品的价值 double c; //单位重量的价值，v/w }a[1001]; bool cmp(bag a, bag b){ return a.c >= b.c; } double knapsack(int n, bag a[], double c){ double cleft=c; int i=0; double b=0; while(i<n && a[i].w<cleft){ cleft -= a[i].w; b += a[i].v; i++; } //装满背包的剩余空间 if (i<n) b += 1.0*a[i].v*cleft/a[i].w; return b; } int main() { int i; for(i=0;i<7;i++){ cin>>a[i].w>>a[i].v; a[i].c=a[i].v/a[i].w; } sort(a,a+i,cmp); cout<<"最大价值为:"<<knapsack(7,a,20); return 0; }