Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int weights[30],prices[100],arr[1005][1005];
- int sale(int maxi_weight, int weight, int index, int price ,int num_objects2)
- {
- if(index == num_objects2 && weight <= maxi_weight)
- return arr[index][weight] = price;
- else if(index == num_objects2)
- return arr[index][weight] = -1;
- 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));
- }
- int main()
- {
- int testcases,i,j,num_people,max_weight,sum=0,num_objects;
- for(i=0;i<1005;i++)
- for(j=0;j<1005;j++)
- arr[i][j] = -1;
- cin >> testcases;
- for(i=0;i<testcases;i++)
- {
- cin >> num_objects;
- for(j=0;j<num_objects;j++)
- cin >> prices[j] >> weights [j];
- cin >> num_people;
- for(j=0;j<num_people;j++)
- {
- cin >> max_weight;
- sum += sale(max_weight,0,0,0,num_objects) << endl;
- }
- cout << sum << endl;
- sum = 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement