fork(3) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. struct product{
  5.     int weight;
  6.     int value;
  7.     string name;
  8. };
  9. int main()
  10. {
  11.     int maxweight, n;
  12.     cin >> maxweight >> n;
  13.     int table[maxweight + 1][n + 1],fromwhere[maxweight + 1][n + 1];
  14.     product A[n];
  15.     for (int i = 0;i < n;i ++)
  16.     {
  17.         cin >> A[i].name >> A[i].weight >> A[i].value;
  18.     }
  19.     for (int x = 0;x < maxweight + 1;x ++)
  20.     {
  21.         table[x][0] = 0;
  22.     }
  23.     for (int y = 0;y < maxweight + 1;y ++)
  24.     {
  25.         table[0][y] = 0;
  26.     }
  27.     for (int y = 1;y < n + 1;y ++)
  28.     {
  29.         for (int x = 1;x < maxweight + 1;x ++)
  30.         {
  31.             if (A[y - 1].weight > x)
  32.             {
  33.                 table[x][y] = table[x][y - 1];
  34.                 fromwhere[x][y] = x;
  35.             }
  36.             else
  37.             {
  38.                 if(table[x][y - 1] > A[y - 1].value + table[x - A[y - 1].weight][y - 1])
  39.                 {
  40. //cout << table[x][y - 1] << " " << A[y - 1].value + table[x - A[y - 1].weight][y] << endl;
  41.                     table[x][y] = table[x][y - 1];
  42.                     fromwhere[x][y] = x;
  43.                 }
  44.                 else
  45.                 {
  46.  
  47.                     table[x][y] = A[y - 1].value + table[x - A[y - 1].weight][y - 1];
  48.                     fromwhere[x][y] = x - A[y - 1].weight;
  49.                 }
  50.             }
  51.         }
  52.     }
  53.     int maxnum = table[0][n], index = 0;
  54.     for (int i = 0;i < maxweight + 1;i ++)
  55.     {
  56.         //cout << table[i][n]
  57.         if(table[i][n] >= maxnum)
  58.         {
  59.             index = i;
  60.             maxnum = table[i][n];
  61.         }
  62.     }
  63.     cout << maxnum << endl;
  64.  
  65.     int c = index;
  66.  
  67.     for (int y = n ;table[c][y] != 0;y --)
  68.     {
  69.         //cout << " " << table[c][y] << " " << table[c][y - 1];
  70.         if (table[c][y] != table[c][y - 1])
  71.         {
  72.             //cout << c << " ";
  73.             cout << A[y - 1].name << endl;
  74.             c = fromwhere[c][y];
  75.  
  76.         }
  77.         else
  78.         {
  79.             c = fromwhere[c][y];
  80.         }
  81.     }
  82.     return 0;
  83. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
15
3
salad 14 9
burger 15 12
candy 1 3
stdout
copy 
12
salad
https://ideone.com/hVV3lG
language:
C++ (gcc 8.3)
created:
11 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!