Advertisement
Guest User

Untitled

a guest
Jan 16th, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. /*
  2. ID: mohd_sh2
  3. LANG: C++11
  4. TASK: holstein
  5. */
  6.  
  7. #include <iostream>
  8. #include <fstream>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <set>
  12. #include <climits>
  13. using namespace std;
  14. typedef vector<int> vi;
  15.  
  16. int V, G;
  17.  
  18. struct Feed {
  19.  
  20. int val[30];
  21.  
  22. bool is_met_req() {
  23. for(int i=0; i<V; i++) if(val[i]>0) return false;
  24. return true;
  25. }
  26.  
  27. bool operator>(Feed &b) {
  28. for(int i=0; i<V; i++) if(val[i]<=b.val[i]) return false;
  29. return true;
  30. }
  31.  
  32. bool operator==(Feed &b) {
  33. for(int i=0; i<V; i++) if(val[i]!=b.val[i]) return false;
  34. return true;
  35. }
  36.  
  37. Feed operator-(Feed &b) {
  38. Feed newf;
  39. for(int i=0; i<V; i++) newf.val[i] = val[i] - b.val[i];
  40. return newf;
  41. }
  42. };
  43.  
  44. Feed req, each[20];
  45.  
  46. // find minimum feeding
  47. Feed min_feed;
  48. vi iproc_min;
  49.  
  50. // store solved list
  51. set<vi> computed;
  52.  
  53. // iproc = processed index
  54. void solve(Feed leftover, vi iproc) {
  55.  
  56. if(leftover.is_met_req()) { // if below or eq zero
  57.  
  58. // 1) little feed number
  59. if(iproc.size() < iproc_min.size()) {
  60. min_feed = leftover;
  61. iproc_min = iproc;
  62. }
  63.  
  64. // 1) minimum feed
  65. if(leftover > min_feed) {
  66. min_feed = leftover;
  67. iproc_min = iproc;
  68. }
  69.  
  70. return;
  71. }
  72.  
  73. // brute-force all subsets
  74. for(int i=0; i<G; i++) {
  75. if(find(iproc.begin(), iproc.end(), i) == iproc.end()) {
  76.  
  77. vi niproc(iproc);
  78. niproc.push_back(i);
  79. sort(niproc.begin(), niproc.end());
  80.  
  81. // if we have not yet to solve
  82. // essence of dynamic programming =)
  83. if(computed.find(niproc) == computed.end()) {
  84. computed.insert(niproc); // mark that we already solved this subset
  85. solve(leftover - each[i], niproc);
  86. }
  87. }
  88. }
  89. }
  90.  
  91. int main() {
  92.  
  93. #ifndef STDIN
  94. freopen("holstein.out", "w", stdout);
  95. freopen("holstein.in", "r", stdin);
  96. #endif
  97.  
  98. cin >> V;
  99. for(int i=0; i<V; i++)
  100. cin >> req.val[i];
  101.  
  102. cin >> G;
  103. for(int i=0; i<G; i++)
  104. for(int j=0; j<V; j++)
  105. cin >> each[i].val[j];
  106.  
  107. // initialize min_feed
  108. for(int i=0; i<V; i++) min_feed.val[i] = INT_MIN;
  109.  
  110. // recursively solve the problem
  111. vi leftover;
  112. solve(req, leftover);
  113.  
  114. // print out answers
  115. cout << iproc_min.size() << ' ';
  116. for(int i=0; i<iproc_min.size(); i++) {
  117. if(i>0) cout << ' ';
  118. cout << iproc_min[i]+1;
  119. }
  120.  
  121. cout << endl;
  122.  
  123. return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement