这题对我来说有些难，参考了学长的代码，所以让我写“我的思路”肯定会心虚的，就把原文地址贴过来了。核心思想是用f[i]表示能叠 i 层时最轻的总重量，每次扫描的时候都会更新f[i]。这是原文：http://www.cnblogs.com/staginner/archive/2011/11/30/2268497.html
代码自己改了一下，本来想把qsort改成sort的，但是毕竟很久没接触qsort了，就没做太大的改动，当作复习qsort。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #define MAXN 5700 5 #define INF 1000000 6 int w[MAXN],s[MAXN],r[MAXN],f[MAXN]; 7 int cmp(const void *_q,const void *_p) 8 { 9 int *q = (int *)_q; 10 int *p = (int *)_p; 11 return s[*q] - s[*p]; 12 } 13 int main() 14 { 15 int i,j,max,n = 0; 16 while(scanf("%d%d",&w[n],&s[n])==2) 17 if(s[n] >= w[n]) 18 n++; 19 for(i = 0; i <= n; i++) 20 f[i] = INF, r[i] = i; 21 f[0] = max = 0; 22 qsort(r,n,sizeof(r[0]),cmp); 23 for(i = 0; i < n; i++) 24 for(j = max; j >= 0; j--) 25 { 26 if(w[r[i]] + f[j] <= s[r[i]] && f[j] + w[r[i]] < f[j+1]) 27 { 28 f[j+1] = f[j] + w[r[i]]; 29 if(j+1 > max) 30 max = j+1; 31 } 32 } 33 printf("%d\n",max); 34 return 0; 35 }