算法导论-16.2-6

题目：

说明如何在O(n)时间内解决部分背包问题

思考：

http://www.cnblogs.com/meteorgan/archive/2012/04/22/2459117.html

常规算法：

先求avgi = vi/wi，按照avgi从大到小排序，再贪心选择，时间复杂度为O(nlgn)

改进：

更一般的情况，不需要排序，例如:如果a1, a2，a3是avgi 最大的三个物品，如果它们的总量和不大于W，我们是不需要知道它们间的相对顺序的。

O(n)算法：

选择一个物品作为主元，对所有物品进行Paitition操作。将avg 分为三个集合G = {ai: avgi < m}, Q = {ai： avgi = m}, P = {ai: avgi > m}。分别对G, Q, P中元素求和得SG, SQ, SP。

1. 如果W < SG, 则令物体的集合为O = G，对集合O递归进行上述过程。

2. 如果 SG<=W <= SG+SQ，则将集合G中的元素都放入包中，并将集合Q总元素尽可能多的放入包中，结束。

3. 如果 SG+SQ < W, 将G，Q中元素放入包中。令物体集合O = P，总重W = W - SG - SQ。递归进行上述过程。

代码：

#include <iostream>using namespace std;#define N 10//物品信息struct node{int weight;int value;};int Partition(node *A, int p, int r){node x = A[r];int i = p-1, j;for(j = p; j < r; j++){//划分的依据是avg = value / weightdouble t1 = x.value * 1.0 / x.weight;double t2 = A[j].value * 1.0 / A[j].weight;if(t2 >= t1){i++;swap(A[i], A[j]);}}swap(A[i+1], A[r]);return i+1;}int Randomized_Partition(node *A, int p, int r){//随机选择数组中一个数作为主元int i = rand() % (r-p+1) + p;swap(A[r], A[i]);//划分return Partition(A, p, r);}//i是从1开使计数的，不是从p开始int Randomized_Select(node *A, int p, int r, int weight, int value){if(p == r)return A[p].value;//以某个元素为主元，把数组分为两组，A[p..q-1] < A[q] < A[q+1..r]，返回主元在整个数组中的位置int q = Randomized_Partition(A, p, r);//主元是整个数组中的第q个元素int i, w = 0, v = 0;//求SGfor(i = p; i < q; i++){w = w + A[i].weight;v = v + A[i].value;}if(w == weight)//正是所求的元素return value;//主元物品取一部分else if(w < weight && w + A[q].weight >= weight)return value + A[q].value * (weight-w) / A[q].weight;else if(w > weight)//所求元素<主元，则在A[p..q-1]中继续寻找return Randomized_Select(A, p, q-1, w, value);else//所求元素>主元，则在A[q+1..r]中继续寻找return Randomized_Select(A, q+1, r, weight - w - A[q].weight, value + v);}int main(){node A[N+1];int i;for(i = 1; i <= N; i++)cin>>A[i].weight>>A[i].value;return 0;}