1. /*
2.  
3. // Job sequencing
4.  
5. #include <algorithm>
6. #include <iostream>
7. using namespace std;
8.  
9. struct Job {
10.  
11.     char id;
12.     int dead;
13.     int profit;
14.                
15. };
16.  
17. bool comparison(Job a, Job b)
18. {
19.     return (a.profit > b.profit);
20. }
21.  
22. void printJobScheduling(Job arr[], int n)
23. {
24.     sort(arr, arr + n, comparison);
25.  
26.     int result[n];
27.     bool slot[n];
28.     for (int i = 0; i < n; i++)
29.         slot[i] = false;
30.     for (int i = 0; i < n; i++) {
31.         for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
32.  
33.             if (slot[j] == false) {
34.                 result[j] = i; // Add this job to result
35.                 slot[j] = true; // Make this slot occupied
36.                 break;
37.             }
38.         }
39.     }
40.  
41.     for (int i = 0; i < n; i++)
42.         if (slot[i])
43.             cout << arr[result[i]].id << " ";
44. }
45.  
46. int main()
47. {
48.     Job jj;
49.     Job arr[100];
50.     for(int i=0;i<5;i++)
51.     {
52.         cin>>jj.id>>jj.dead>>jj.profit;
53.         arr[i]={jj.id,jj.dead,jj.profit};
54.  
55.     }
56.     // Job arr[] = { { 'a', 2, 100 },
57.     //             { 'b', 1, 19 },
58.     //             { 'c', 2, 27 },
59.     //             { 'd', 1, 25 },
60.     //             { 'e', 3, 15 } };
61.    
62.     int n = 5;
63.     cout << "Following is maximum profit sequence of jobs "
64.             "\n";
65.  
66.     printJobScheduling(arr, n);
67.     return 0;
68. }
69.  
70.  
71.  
72. // Activityy Selection
73.  
74. #include <bits/stdc++.h>
75.  
76. using namespace std;
77.  
78. struct Activity
79. {
80.     int start, finish;
81. };
82.  
83. // This function is used for sorting activities according to finish time
84. bool Sort_activity(Activity s1, Activity s2)
85. {
86.     return (s1.finish< s2.finish);
87. }
88.  
89. /*  Prints maximum number of activities that can
90.     be done by a single person or single machine at a time.
91. */
92. void print_Max_Activities(Activity arr[], int n)
93. {
94.     // Sort activities according to finish time
95.     sort(arr, arr+n, Sort_activity);
96.  
97.     cout<< "Following activities are selected \n";
98.  
99.     // Select the first activity
100.     int i = 0;
101.     cout<< "(" <<arr[i].start<< ", " <<arr[i].finish << ")\n";
102.  
103.     // Consider the remaining activities from 1 to n-1
104.     for (int j = 1; j < n; j++)
105.     {
106.         // Select this activity if it has start time greater than or equal
107.         // to the finish time of previously selected activity
108.         if (arr[j].start>= arr[i].finish)
109.         {    
110.             cout<< "(" <<arr[j].start<< ", "<<arr[j].finish << ") \n";
111.             i = j;
112.         }
113.     }
114. }
115.  
116. // Driver program
117. int main()
118. {
119.     Activity arr[6];
120.     for(int i=0; i<6; i++)
121.     {
122.         cout<<"Enter the start and end time of "<<i+1<<" activity \n";
123.         cin>>arr[i].start>>arr[i].finish;
124.     }
125.  
126.     print_Max_Activities(arr, N);
127.     return 0;
128. }
129.  
130.  
131. // C++ program to solve knapsack problem using
132. // branch and bound
133. #include <bits/stdc++.h>
134. using namespace std;
135.  
136. // Structure for Item which store weight and corresponding
137. // value of Item
138. struct Item
139. {
140.  float weight;
141.  int value;
142. };
143.  
144. // Node structure to store information of decision
145. // tree
146. struct Node
147. {
148.  // level --&gt; Level of node in decision tree (or index
149.  //    in arr[]
150.  // profit --&gt; Profit of nodes on path from root to this
151.  //   node (including this node)
152.  // bound ---&gt; Upper bound of maximum profit in subtree
153.  //   of this node/
154.  int level, profit, bound;
155.  float weight;
156. };
157.  
158. // Comparison function to sort Item according to
159. // val/weight ratio
160. bool cmp(Item a, Item b)
161. {
162.  double r1 = (double)a.value / a.weight;
163.  double r2 = (double)b.value / b.weight;
164.  return r1 > r2;
165. }
166.  
167.  
168.  
169. // knapsack Using branch and bound
170.  
171. int bound(Node u, int n, int W, Item arr[])
172. {
173.  // if weight overcomes the knapsack capacity, return
174.  // 0 as expected bound
175.  if (u.weight >= W)
176.   return 0;
177.  
178.  // initialize bound on profit by current profit
179.  int profit_bound = u.profit;
180.  
181.  // start including items from index 1 more to current
182.  // item index
183.  int j = u.level + 1;
184.  int totweight = u.weight;
185.  
186.  // checking index condition and knapsack capacity
187.  // condition
188.  while ((j < n) && (totweight + arr[j].weight <= W))
189.  {
190.   totweight += arr[j].weight;
191.   profit_bound += arr[j].value;
192.   j++;
193.  }
194.  
195.  // If k is not n, include last item partially for
196.  // upper bound on profit
197.  if (j < n)
198.   profit_bound += (W - totweight) * arr[j].value /
199.           arr[j].weight;
200.  
201.  return profit_bound;
202. }
203.  
204. // Returns maximum profit we can get with capacity W
205. int knapsack(int W, Item arr[], int n)
206. {
207.  // sorting Item on basis of value per unit
208.  // weight.
209.  sort(arr, arr + n, cmp);
210.  
211.  // make a queue for traversing the node
212.  queue<Node> Q;
213.  Node u, v;
214.  
215.  // dummy node at starting
216.  u.level = -1;
217.  u.profit = u.weight = 0;
218.  Q.push(u);
219.  
220.  // One by one extract an item from decision tree
221.  // compute profit of all children of extracted item
222.  // and keep saving maxProfit
223.  int maxProfit = 0;
224.  while (!Q.empty())
225.  {
226.   // Dequeue a node
227.   u = Q.front();
228.   Q.pop();
229.  
230.   // If it is starting node, assign level 0
231.   if (u.level == -1)
232.    v.level = 0;
233.  
234.   // If there is nothing on next level
235.   if (u.level == n-1)
236.    continue;
237.  
238.   // Else if not last node, then increment level,
239.   // and compute profit of children nodes.
240.   v.level = u.level + 1;
241.  
242.   // Taking current level's item add current
243.   // level's weight and value to node u's
244.   // weight and value
245.   v.weight = u.weight + arr[v.level].weight;
246.   v.profit = u.profit + arr[v.level].value;
247.  
248.   // If cumulated weight is less than W and
249.   // profit is greater than previous profit,
250.   // update maxprofit
251.   if (v.weight <= W && v.profit > maxProfit)
252.    maxProfit = v.profit;
253.  
254.   // Get the upper bound on profit to decide
255.   // whether to add v to Q or not.
256.   v.bound = bound(v, n, W, arr);
257.  
258.   // If bound value is greater than profit,
259.   // then only push into queue for further
260.   // consideration
261.   if (v.bound > maxProfit)
262.    Q.push(v);
263.  
264.   // Do the same thing, but Without taking
265.   // the item in knapsack
266.   v.weight = u.weight;
267.   v.profit = u.profit;
268.   v.bound = bound(v, n, W, arr);
269.   if (v.bound > maxProfit)
270.    Q.push(v);
271.  }
272.  
273.  return maxProfit;
274. }
275.  
276. // driver program to test above function
277. int main()
278. {
279.  int W = 10; // Weight of knapsack
280.  Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
281.     {5, 95}, {3, 30}};
282.  int n = sizeof(arr) / sizeof(arr[0]);
283.  
284.  cout << "Maximum possible profit = "
285.   << knapsack(W, arr, n);
286.  
287.  return 0;
288. }
289.  
290.  
291. // knapsack using DP
292.  
293. // CPP code for Dynamic Programming based
294. // solution for 0-1 Knapsack problem
295. #include <bits/stdc++.h>
296. #include <iostream>
297. using namespace std;
298.  
299. // A utility function that returns maximum of two integers
300. int max(int a, int b) { return (a > b) ? a : b; }
301.  
302. // Prints the items which are put in a knapsack of capacity W
303. void printknapSack(int W, int wt[], int val[], int n)
304. {
305.  int i, w;
306.  int K[n + 1][W + 1];
307.  
308.  // Build table K[][] in bottom up manner
309.  for (i = 0; i <= n; i++) {
310.   for (w = 0; w <= W; w++) {
311.    if (i == 0 || w == 0)
312.     K[i][w] = 0;
313.    else if (wt[i - 1] <= w)
314.     K[i][w] = max(val[i - 1] +
315.      K[i - 1][w - wt[i - 1]], K[i - 1][w]);
316.    else
317.     K[i][w] = K[i - 1][w];
318.   }
319.  }
320.  
321.  // stores the result of Knapsack
322.  int res = K[n][W];
323.  cout<< res << endl;
324.  
325.  w = W;
326.  for (i = n; i > 0 && res > 0; i--) {
327.  
328.   // either the result comes from the top
329.   // (K[i-1][w]) or from (val[i-1] + K[i-1]
330.   // [w-wt[i-1]]) as in Knapsack table. If
331.   // it comes from the latter one/ it means
332.   // the item is included.
333.   if (res == K[i - 1][w])
334.    continue;
335.   else {
336.  
337.    // This item is included.
338.    cout<<" "<<wt[i - 1] ;
339.    
340.    // Since this weight is included its
341.    // value is deducted
342.    res = res - val[i - 1];
343.    w = w - wt[i - 1];
344.   }
345.  }
346. }
347.  
348. // Driver code
349. int main()
350. {
351.  int val[] = { 60, 100, 120 };
352.  int wt[] = { 10, 20, 30 };
353.  int W = 50;
354.  int n = sizeof(val) / sizeof(val[0]);
355.  
356.  printknapSack(W, wt, val, n);
357.  
358.  return 0;
359. }
360.  
361.  
362. // matrix chain multiplication using recursion
363.  
364. #include <bits/stdc++.h>
365. using namespace std;
366.  
367. // Matrix Ai has dimension p[i-1] x p[i]
368. // for i = 1 . . . n
369. int MatrixChainOrder(int p[], int i, int j)
370. {
371.  if (i == j)
372.   return 0;
373.  int k;
374.  int mini = INT_MAX;
375.  int count;
376.  
377.  // Place parenthesis at different places
378.  // between first and last matrix,
379.  // recursively calculate count of multiplications
380.  // for each parenthesis placement
381.  // and return the minimum count
382.  for (k = i; k < j; k++)
383.  {
384.   count = MatrixChainOrder(p, i, k)
385.     + MatrixChainOrder(p, k + 1, j)
386.     + p[i - 1] * p[k] * p[j];
387.  
388.   mini = min(count, mini);
389.  }
390.  
391.  // Return minimum count
392.  return mini;
393. }
394.  
395. // Driver Code
396. int main()
397. {
398.  int arr[] = { 1, 2, 3, 4, 3 };
399.  int N = sizeof(arr) / sizeof(arr[0]);
400.  
401.  // Function call
402.  cout << "Minimum number of multiplications is "
403.   << MatrixChainOrder(arr, 1, N - 1);
404.  return 0;
405. }
406.  
407.  
408.  
409. // N-Queen
410. #include<iostream>
411. using namespace std;
412. #define N 4
413. void printBoard(int board[N][N]) {
414.    for (int i = 0; i < N; i++) {
415.       for (int j = 0; j < N; j++)
416.          cout << board[i][j] << " ";
417.          cout << endl;
418.    }
419. }
420. bool isValid(int board[N][N], int row, int col) {
421.    for (int i = 0; i < col; i++) //check whether there is queen in the left or not
422.       if (board[row][i])
423.          return false;
424.    for (int i=row, j=col; i>=0 && j>=0; i--, j--)
425.       if (board[i][j]) //check whether there is queen in the left upper diagonal or not
426.          return false;
427. for (int i=row, j=col; j>=0 && i<N; i++, j--)
428.       if (board[i][j]) //check whether there is queen in the left lower diagonal or not
429.          return false;
430.    return true;
431. }
432. bool solveNQueen(int board[N][N], int col) {
433.    if (col >= N) //when N queens are placed successfully
434.       return true;
435.    for (int i = 0; i < N; i++) { //for each row, check placing of queen is possible or not
436.       if (isValid(board, i, col) ) {
437.          board[i][col] = 1; //if validate, place the queen at place (i, col)
438.          if ( solveNQueen(board, col + 1)) //Go for the other columns recursively
439.             return true;
440.          board[i][col] = 0; //When no place is vacant remove that queen
441.       }
442.    }
443.    return false; //when no possible order is found
444. }
445. bool checkSolution() {
446.    int board[N][N];
447.    for(int i = 0; i<N; i++)
448.    for(int j = 0; j<N; j++)
449.    board[i][j] = 0; //set all elements to 0
450.    if ( solveNQueen(board, 0) == false ) { //starting from 0th column
451.       cout << "Solution does not exist";
452.       return false;
453.    }
454.    printBoard(board);
455.    return true;
456. }
457. int main() {
458.    checkSolution();
459. }
460.  
461.  
462.  
463. // Graph Coloring
464.  
465. #include<bits/stdc++.h>
466.  
467. using namespace std;
468.  
469. int n,e,i,j;
470. vector<vector<int> > graph;
471. vector<int> color;
472. bool vis[100011];
473.  
474. void greedyColoring()
475. {
476.     color[0]  = 0;
477.     for (i=1;i<n;i++)
478.         color[i] = -1;
479.  
480.     bool unused[n];
481.  for (i=0;i<n;i++)
482.         unused[i]=0;
483.  
484.  
485.     for (i = 1; i < n; i++)
486.     {
487.         for (j=0;j<graph[i].size();j++)
488.             if (color[graph[i][j]] != -1)
489.                 unused[color[graph[i][j]]] = true;
490.         int cr;
491.         for (cr=0;cr<n;cr++)
492.             if (unused[cr] == false)
493.                 break;
494.   color[i] = cr;
495.  
496.         for (j=0;j<graph[i].size();j++)
497.             if (color[graph[i][j]] != -1)
498.                 unused[color[graph[i][j]]] = false;
499.     }
500. }
501. int main()
502. {
503.     int x,y;
504.     cout<<"Enter number of vertices and edges respectively:";
505.     cin>>n>>e;
506.     cout<<"\n";
507.     graph.resize(n);
508.     color.resize(n);
509.     memset(vis,0,sizeof(vis));
510.     for(i=0;i<e;i++)
511.     {
512.         cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
513.         cin>>x>>y;
514.         x--; y--;
515.         graph[x].push_back(y);
516.         graph[y].push_back(x);
517.     }
518. greedyColoring();
519.     for(i=0;i<n;i++)
520.     {
521.         cout<<"Vertex "<<i+1<<" is coloured "<<color[i]+1<<"\n";
522.     }
523. }
524.  
525.  
526.  
527. // Subset Sum
528.  
529. #include <bits/stdc++.h>
530. using namespace std;
531.  
532. // Print all subsets if there is atleast one subset of set[]
533. // with sum equal to given sum
534. bool flag = 0;
535. void PrintSubsetSum(int i, int n, int set[], int targetSum,
536.      vector<int>& subset)
537. {
538.  // targetSum is zero then there exist a
539.  // subset.
540.  if (targetSum == 0) {
541.  
542.   // Prints valid subset
543.   flag = 1;
544.   cout << "[ ";
545.   for (int i = 0; i < subset.size(); i++) {
546.    cout << subset[i] << " ";
547.   }
548.   cout << "]";
549.   return;
550.  }
551.  
552.  if (i == n) {
553.   // return if we have reached at the end of the array
554.   return;
555.  }
556.  
557.  // Not considering current element
558.  PrintSubsetSum(i + 1, n, set, targetSum, subset);
559.  
560.  // consider current element if it is less than or equal
561.  // to targetSum
562.  if (set[i] <= targetSum) {
563.  
564.   // push the current element in subset
565.   subset.push_back(set[i]);
566.  
567.   // Recursive call for consider current element
568.   PrintSubsetSum(i + 1, n, set, targetSum - set[i],
569.      subset);
570.  
571.   // pop-back element after recursive call to restore
572.   // subsets original configuration
573.   subset.pop_back();
574.  }
575. }
576.  
577. // Driver code
578. int main()
579. {
580.  // Test case 1
581.  int set[] = { 1, 2, 1 };
582.  int sum = 3;
583.  int n = sizeof(set) / sizeof(set[0]);
584.  vector<int> subset;
585.  cout << "Output 1:" << endl;
586.  PrintSubsetSum(0, n, set, sum, subset);
587.  cout << endl;
588.  flag = 0;
589.  // Test case 2
590.  int set2[] = { 3, 34, 4, 12, 5, 2 };
591.  int sum2 = 30;
592.  int n2 = sizeof(set) / sizeof(set[0]);
593.  vector<int> subset2;
594.  cout << "Output 2:" << endl;
595.  PrintSubsetSum(0, n2, set2, sum2, subset2);
596.  if (!flag) {
597.   cout << "There is no such subset";
598.  }
599.  
600.  return 0;
601. }
602.  
603.  
604. // Topological sort
605.  
606. #include <bits/stdc++.h>
607. using namespace std;
608.  
609. void topo_sort(int vertices, int edges) {
610.     vector<char> ans;
611.     queue<char> q;
612.     map<char, vector<char>> graph;
613.     map<char, int> inDegree;
614.  
615.     vector<pair<char, char>> edgeList = {{'A', 'B'},{'A', 'C'},{'B', 'D'},{'B', 'E'},{'C', 'E'},{'D', 'F'},{'E', 'F'}};
616.  
617.     for (int i = 0; i < edges; i++) {
618.         char a = edgeList[i].first;
619.         char b = edgeList[i].second;
620.         graph[a].push_back(b);
621.         inDegree[b]++;
622.     }
623.  
624.     for (char c = 'A'; c <= 'F'; c++) if (inDegree[c] == 0) q.push(c);
625.  
626.     while (!q.empty()) {
627.         char v = q.front();
628.         q.pop();
629.         ans.push_back(v);
630.         for (int i = 0; i < graph[v].size(); i++) {
631.             char u = graph[v][i];
632.             inDegree[u]--;
633.             if (inDegree[u] == 0) {
634.                 q.push(u);
635.             }
636.         }
637.     }
638.  
639.     for (int i = 0; i < ans.size(); i++) {
640.         cout << ans[i];
641.         if (i < ans.size() - 1)  cout << "->";
642.     }
643. }
644.  
645. int main() {
646.     int vertices = 6;
647.     int edges = 7;
648.     topo_sort(vertices, edges);
649.     return 0;
650. }
651.  
652.  
653.  
654.  
655.  
656.  
657. */
658.