SHARE
TWEET

Untitled

a guest Sep 7th, 2012 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3. int weights[30],prices[100],arr[1005][1005];
  4. int sale(int maxi_weight, int weight, int index, int price ,int num_objects2)
  5. {
  6.         if(index == num_objects2 && weight <= maxi_weight)
  7.                 return arr[index][weight] = price;
  8.         else if(index == num_objects2)
  9.                 return arr[index][weight] = -1;
  10.         return  arr[index][weight] = max(sale(maxi_weight, weight + weights[index], index+1 ,price + prices[index],num_objects2), sale(maxi_weight, weight, index + 1 , price, num_objects2));
  11. }
  12. int main()
  13. {
  14.         int testcases,i,j,num_people,max_weight,sum=0,num_objects;
  15.         for(i=0;i<1005;i++)
  16.                 for(j=0;j<1005;j++)
  17.                         arr[i][j] = -1;
  18.         cin >> testcases;
  19.         for(i=0;i<testcases;i++)
  20.         {
  21.                 cin >> num_objects;
  22.                 for(j=0;j<num_objects;j++)
  23.                         cin >> prices[j] >> weights [j];
  24.                 cin >> num_people;
  25.                 for(j=0;j<num_people;j++)
  26.                 {
  27.                         cin >> max_weight;
  28.                         sum += sale(max_weight,0,0,0,num_objects) << endl;
  29.                 }
  30.                 cout << sum << endl;
  31.                 sum = 0;
  32.         }
  33.         return 0;
  34. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top