给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 wi ，价值vi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。 当作0-1背包问题，用动态规划算法，获得最优值220； 当作0-1背包问题，用贪心算法，按性价比从高到底顺序选取物品，获得最优值160。由于物品不可分割，剩下的空间白白浪费。 当作背包问题，用贪心算法，按性价比从高到底的顺序选取物品，获得最优值240。由于物品可以分割，剩下的空间装入物品3的一部分，而获得了更好的性能。 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.0a[i].vcleft/a[i].w; return b; }
