language: C++ 4.7.2 (gcc-4.7.2)
date: 126 days 5 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# include <cstdio>
# include <algorithm>
# include <cstring>
# define DEBUG printf
using namespace std;
int Budget, Total, Entry [100], Fun [100], DPTable [101][2501], MaxFun, MinEntry, i, j;
int main()
{
   //freopen ("Input.txt", "r", stdin);
   //freopen ("Output.txt","w", stdout);
   scanf ("%d%d", &Budget, &Total);
   while (Budget && Total)
   {
      for (i = 0; i < Total; i++) scanf ("%d%d", &Entry [i], &Fun [i]);
 
      memset (DPTable, -1, sizeof DPTable);
      for (i = 0; i <= Total; i++) DPTable [i][0] = 0;
      for (i = 0; i <= Budget;i++) DPTable [0][i] = 0;
      MaxFun = -1;
 
      for (i = 1; i <= Total; i++)
         for (j = 1; j <= Budget; j++)
         {
            DPTable [i][j] = DPTable [i-1][j];
            if (j - Entry [i-1] >= 0 && DPTable [i-1][j-Entry[i-1]] != -1)
            {
               DPTable [i][j] = max (DPTable [i-1][j], DPTable [i-1][j-Entry[i-1]] + Fun [i-1]);
               if (DPTable [i][j] > MaxFun || (DPTable [i][j] == MaxFun && j < MinEntry))
               {
                  MaxFun = DPTable [i][j]; MinEntry = j;
               }
           }
         }
      printf ("%d %d\n", MinEntry, MaxFun);
      scanf ("%d%d", &Budget, &Total);
   }
   return 0;
}