fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6.  
  7. vector< vector<int> > dp(1000, vector<int>(10001, -1));
  8. int maxProfit(vector< pair<int, int> >& bags, int maxWeight, int index) {
  9.     if (index == bags.size()) {
  10.         return 0;
  11.     }
  12.     if (dp[index][maxWeight] != -1) {
  13.         return dp[index][maxWeight];
  14.     }
  15.     if (bags[index].first > maxWeight) {
  16.         return dp[index][maxWeight] = maxProfit(bags, maxWeight, index + 1);
  17.     }
  18.     int selected = bags[index].second + maxProfit(bags, maxWeight - bags[index].first, index + 1);
  19.     int notSelected = maxProfit(bags, maxWeight, index + 1);
  20.     return dp[index][maxWeight] = max(selected, notSelected);
  21. }
  22. int getMaxProfit(vector<pair <int, int> >& bags, int maxWeight) {
  23.     // dp.resize(bags.size(), vector<int>(maxWeight + 1, -1));
  24.     return maxProfit(bags, maxWeight, 0);
  25. }
  26.  
  27. int main() {
  28.  
  29.     int nInstances;
  30.     // printf("Enter number of instances: \n");
  31.     cin >> nInstances;
  32.     while (nInstances--) {
  33.         int maxWeight;
  34.         int nBags;
  35.         // printf("Enter max weight of the truck: \n");
  36.         cin >> maxWeight >> nBags;
  37.         vector<pair<int, int> > bags(nBags);
  38.         for (int i = 0; i < nBags; i++) {
  39.             int weight;
  40.             int profit;
  41.             // printf("Enter weight and profit of bag %d: \n", i + 1);
  42.             cin >> weight >> profit;
  43.             bags[i].first = weight;
  44.             bags[i].second = profit;
  45.         }
  46.         cout << "Hey stupid robber, you can get: " + getMaxProfit(bags, maxWeight);
  47.     }
  48. }
  49.  
Success #stdin #stdout 0.02s 42120KB
comments (?)
stdin 
3
34 5
178 12
30 1
13 7
34 8
87 6
900 1
900 25
100 10
27 16
131 9
132 17
6 5
6 23
56 21
100 25
1 25
25 25
100 2
stdout 
id robber, you can get: n get:
https://ideone.com/oXLMbk
problem WACHOVIA, based on SPOJ submission 34008401 (C++ 4.3.2), 2024-12-24 20:52:44
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 day 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!