UVA_624

    实际就是0-1背包的问题，把时间等效成体积和价值就可以了。需要注意的是总时间的那个维度要开大一点，10000就够用了。

#include
     
       #include
      
        #define MAXN 30 #define MAXD 10010 int M, N, a[MAXN], p[MAXN][MAXD], f[MAXN][MAXD]; void init() {
   int i;     scanf("%d", &N); for(i = 1; i <= N; i ++)         scanf("%d", &a[i]); } void printresult(int i, int j) {
   if(i == 0) return;     printresult(i - 1, p[i][j]); if(p[i][j] < j)         printf("%d ", a[i]); } void solve() {
   int i, j, temp;     memset(f, 0, sizeof(f)); for(i = 1; i <= N; i ++) for(j = 0; j <= M; j ++)         {
               f[i][j] = f[i - 1][j];             p[i][j] = j; if(j >= a[i])             {
                   temp = f[i - 1][j - a[i]] + a[i]; if(temp > f[i][j])                 {
                       p[i][j] = j - a[i];                     f[i][j] = temp;                 }             }         }     printresult(N, M);     printf("sum:%d\n", f[N][M]); } int main() {
   while(scanf("%d", &M) == 1)     {
           init();         solve();     } return 0; }