HDU 1171(01リュックサック問題)

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1171
分析:
例えばデータ
3
10    2
20    1
30    1
このような降順の配列を得る:30 20 10 10(2つの10は10値の物品が2つあるため)
総価値の半分はバックパック容量で、それから価値の大きいものから選び、現在のバックパックの中で物の価値に入れたいものの価値がバックパック容量より大きい場合、バックパックに入れたいものは入れません
注意点
1.nが負の場合はn==1ではなくループを停止する
2.バックパック容量が小数点以下の場合は、ceil上限をとる
3.配列ソート降順、昇順ではデータの扱いが悪い
特殊データ
3
10    2
20    1
21    1
答え:31   30
コードは次のとおりです.

#include
using namespace std;
int main()
{
   int n;
   while(scanf("%d",&n)!=EOF&&n>=0)
   {
       if(n<0)
        break;
       int x,y;
       int q[100005],len=0;
       double sum=0.0,temp=0.0;
       for(int i=0;i)
       {
           scanf("%d %d",&x,&y);
           sum=sum+(double)x*y;
           while(y--)
           {
               q[len++]=x;
           }
       }
       temp=ceil(sum*1.0/2.0);
       sort(q,q+len);
       double a=0.0,b=0.0;
       for(int i=len-1;i>=0;i--)
       {
           if(a+q[i]>temp)
            continue;
           a=a+q[i];
       }
       b=sum-a;
       if(b>a)
       {
           int t=a;
           a=b;
           b=t;
       }
       printf("%.0lf %.0lf
",a,b);
   }
}

自分はやっぱり太菜...2時間書きました......