Tarikul_Islam

Sum of Subset Lab

Nov 17th, 2019
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. ///int w[]={10, 7, 5, 18, 12, 20, 15};
  6. int w[50];
  7. int x[50];
  8. int m,n;
  9. int countt=0;
  10.  
  11. class Subset
  12. {
  13. public:
  14.  
  15.  
  16. void sum_of_sub(int s,int k,int r)
  17. {
  18. x[k] = 1;
  19. if(s+w[k] == m)
  20. {
  21. for(int i=0;i<=k;i++)
  22. {
  23. /// cout<<x[i]<<" ";
  24.  
  25. /// For Showing the Weight do below
  26. if(x[i]==1)
  27. cout<<w[i]<<" ";
  28.  
  29. }
  30. cout<<endl;
  31. }
  32.  
  33. else if (s+w[k]+w[k+1]<=m)
  34. sum_of_sub(s+w[k],k+1,r-w[k]);
  35.  
  36. if((((s+r)-w[k])>=m) &&(s+w[k+1])<=m)
  37. {
  38. x[k] = 0;
  39. sum_of_sub(s,k+1,r-w[k]);
  40. }
  41. }
  42.  
  43. void sum(int s,int k,int r)
  44. {
  45. x[k] = 1;
  46. if( s + w[k] > m)
  47. {
  48. display(k);
  49. }
  50. if(s+w[k] == m)
  51. {
  52. //display(k);
  53. }
  54. else if (s+w[k]<=m && k<n)
  55. sum(s+w[k],k+1,r-w[k]);
  56. //cout<<k<<" "<<endl;
  57. if( k<n )
  58. {
  59. x[k] = 0;
  60. sum(s,k+1,r-w[k]);
  61. }
  62. }
  63. void display(int k)
  64. {
  65. for(int i=1;i<=k;i++)
  66. {
  67. if( x[i] == 1)
  68. cout<<w[i]<<" ";
  69. }
  70. cout<<endl;
  71. }
  72.  
  73.  
  74. void five(int s,int k,int r)
  75. {
  76. x[k] = 1;
  77. if(s+w[k] == m && countt<5)
  78. {
  79. countt++;
  80. for(int i=0;i<=k;i++)
  81. {
  82. // cout<<x[i]<<" ";
  83.  
  84. /// For Showing the Weight do below
  85. if(x[i]==1)
  86. cout<<w[i]<<" ";
  87.  
  88. }
  89.  
  90. cout<<endl;
  91. }
  92.  
  93. else if (s+w[k]+w[k+1]<=m)
  94. five(s+w[k],k+1,r-w[k]);
  95.  
  96. if((((s+r)-w[k])>=m) &&(s+w[k+1])<=m)
  97. {
  98. x[k] = 0;
  99. five(s,k+1,r-w[k]);
  100. }
  101. }
  102.  
  103.  
  104.  
  105.  
  106. };
  107.  
  108.  
  109. int main()
  110. {
  111.  
  112. Subset obj;
  113. freopen("in.txt","r",stdin);
  114. int i=0,total_sum = 0;
  115. cin>>m;
  116.  
  117. while(cin)
  118. {
  119. cin>>w[i++];
  120. }
  121.  
  122. for(int j =0;j<i;j++)
  123. total_sum += w[j];
  124.  
  125. obj.five(0,0,total_sum);
  126. //cout<<countt;
  127.  
  128. // cout<<countt;
  129.  
  130.  
  131.  
  132. return 0;
  133. }
Add Comment
Please, Sign In to add comment