fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. using namespace std;
  4. int fun[110], cost[110];
  5. int n, budgt;
  6. int main() {
  7.   while (scanf("%d%d", &budgt, &n) && budgt + n) {
  8.     int dpfun[110][510], dpcost[110][510];
  9.     for (int i = 0; i < n; ++i) scanf("%d%d", &cost[i], &fun[i]);
  10.     for (int i = 0; i < n; ++i)
  11.       for (int j = 0; j <= budgt; ++j) {
  12.         if (j < cost[i]) {
  13.           dpfun[i + 1][j] = dpfun[i][j];
  14.           dpcost[i + 1][j] = dpcost[i][j];
  15.         } else {
  16.           dpfun[i + 1][j] = max(dpfun[i][j], dpfun[i][j - cost[i]] + fun[i]);
  17.           if (dpfun[i][j] < dpfun[i][j - cost[i]] + fun[i]) {
  18.             dpcost[i + 1][j] = dpcost[i][j - cost[i]] + cost[i];
  19.           } else {
  20.             dpcost[i + 1][j] =
  21.                 min(dpcost[i][j - cost[i]] + cost[i], dpcost[i][j]);
  22.           }
  23.         }
  24.       }
  25.     printf("%d %d\n", dpcost[n][budgt], dpfun[n][budgt]);
  26.   }
  27.   return 0;
  28. }
Success #stdin #stdout 0s 3788KB
comments (?)
stdin
copy 
20 4
2 3
8 2
9 5
10 50

0 0
stdout
copy 
19 55
https://ideone.com/5Eeogk
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!