Famous problems

A few recursive and top-down dynamic solutions to famous problems
ShivanshJ · Mar 19, 2017 · 9d47b95 · 9d47b95
1 parent 9564360
commit 9d47b95
Show file tree

Hide file tree

Showing 7 changed files with 519 additions and 0 deletions.
diff --git a/Knapsack (Coin change)_Naive.cpp b/Knapsack (Coin change)_Naive.cpp
@@ -0,0 +1,55 @@
+#include<iostream>
+#include<string.h>
+#include<stdio.h>
+#include<math.h>
+using namespace std;
+
+
+//Given set of coins of RS. 1, 2 AND 5. Count total ways of making a particular sum with those coins.
+
+//Bottom-up dynamic programming. We subtract a denomination from the total sum.
+
+
+#include<limits.h>
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+int ar[]={2,5,3,6};				//Coins available
+int n=sizeof(ar)/sizeof(ar[0]); //Size of array
+
+
+int ct=0;
+//Function passes the sum/weight and the index for array with coins/weights
+int count(int s,int m)
+{	
+	//Here, m<0 as, if we include the element, then m remains the same
+	if(s<0 || m<0)
+		return 0;
+
+ 	if(s==0)
+ 	{
+	 ct++; return 1;
+ 	}	
+
+  // If there are no coins,i.e n=0 and s is greater than 0, then no solution exist
+    if (n <=0 && s >= 1)
+        return 0;
+
+count(s,m-1) ; //Case1: Excluding the element
+count(s-ar[m],m) ; //Case2: Including, For any element we can have as many subtractions.. Ex: sum of 5 can give.. 1,1,1,1,1
+ return 0;
+
+}
+
+
+int main()
+{ 
+	int sum;
+	cout<<"Enter the sum required to be made: ";
+	cin>>sum;
+
+	count(sum,n-1);
+
+	cout<<"The count is: "<<ct;
+
+	return 0;
+}	
diff --git a/Knapsack (Subset problem) type.cpp b/Knapsack (Subset problem) type.cpp
@@ -0,0 +1,74 @@
+#include<iostream>
+#include<string.h>
+#include<stdio.h>
+using namespace std;
+
+//Subset Sum Problem
+//Can the set of numbers be divided into two sets with equal weights
+
+//Explanation: http://www.ideserve.co.in/learn/set-partition-problem-recursion
+
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+int path[256]={0};
+int found=0;
+
+int part(int *ar, int sum,int i, int k)
+{ 	
+	//i<-1, so that last element can run properly, i.e, when part(ar,sum-ar[0],0-1,k+1)
+	if(i<-1 || sum<0)
+	return 0;
+
+//	cout<<sum<<endl;
+
+	path[k]=ar[i];
+
+	if(sum==0)
+	{	found=1;
+	    cout<<"Path is:";
+		F(j,0,k)
+		cout<<path[j]<<" ";
+
+		cout<<endl;
+		return 1;
+	}
+
+
+	//NOTE: Order is important
+	part(ar,sum-ar[i], i-1, k+1);	//Case 2: Including the element[Only once (thus i-1) ] 
+	part(ar,sum,i-1, k); 			//Case 1: Excluding the element
+
+				//In knapsack, coin change .case 2 does not have the "i-1" , part as it does recursion for the same element many times
+				//Here, one element can be subtracted only once			
+return 0;
+}
+
+bool check(int *ar,int sum, int index)
+{ if(sum%2!=0)
+	return false;
+
+
+
+    part(ar,sum/2,index,0);
+    if(found==1)
+	return true;
+
+	return false;
+}
+
+int main()
+{ int ar[]={2,5,8,5};
+
+int n=sizeof(ar)/sizeof(ar[0]);
+int sum=0;
+
+F(i,0,n)
+sum+=ar[i];
+
+if( check(ar,sum,n-1)	)	
+cout<<endl<<"Yes";
+
+else cout<<"No";
+
+return 0;
+}
diff --git a/Knapsack (Thief)_Dynamic.cpp b/Knapsack (Thief)_Dynamic.cpp
@@ -0,0 +1,75 @@
+#include<iostream>
+#include<string.h>
+#include<stdio.h>
+#include<math.h>
+#include<time.h>
+using namespace std;
+
+
+//.......................................Look at Naive for all comments
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+int weight[]={2,3,4,5,6,7};			//Weight of item
+int val[]={3,7,2,9,5,8};			//Value of the items above
+int best=0; 
+
+int save[40][5]={0}; 
+//Save array, here it is taken in the form f save[total weight][index] as shown in the recursion tree
+// http://www.ideserve.co.in/learn/dynamic-programming-0-1-knapsack-problem
+// and then return condition is put : if(save[tot][i]>0 )	return save[tot][i];
+
+int max(int a, int b)
+{ return a>b?:a,b;
+}
+
+int knap(int tot, int i, int cost)
+{ 	
+
+	if(tot<0||i<-1)
+	return 0;
+
+	if(save[tot][i]>0 )
+		return save[tot][i];
+
+
+
+	if(i==-1 || tot==0 )
+	{ if(cost>best)
+		best=cost;
+
+		return best;
+	}	
+
+
+
+	save[tot][i]=knap(tot,i-1,cost) + knap(tot-weight[i], i-1,cost+val[i]); 
+
+	return max(save[i][0],save[i][1]);
+
+}
+
+int main()
+{ 	clock_t t;
+    t = clock();
+
+	int total;
+	cout<<"Enter the total weight the thief can carry: ";
+	cin>>total;
+
+	int n=sizeof(weight)/sizeof(weight[0]); //Size of weight array, as we have to subtract this from total weight
+	if(n-1<=0)
+	{ cout<<"No items available";
+	return 0;
+    }
+
+	knap(total,n-1,0);
+
+	cout<<"The maximum value of things he can carry is :"<<best;
+
+	t=clock()-t;
+	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+
+    printf("\nTook %f seconds to execute \n", time_taken);
+	return 0;
+	return 0;
+}	
diff --git a/Knapsack (Thief)_Naive.cpp b/Knapsack (Thief)_Naive.cpp
@@ -0,0 +1,78 @@
+#include<iostream>
+#include<string.h>
+#include<stdio.h>
+#include<math.h>
+#include<time.h>
+using namespace std;
+
+
+//Given max weight thief can carry. Weights of the items he is stealing. Value of those items. 
+//Find maximum of these values
+
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+int weight[]={2,3,4,5,6,7};			//Weight of item
+int val[]={3,7,2,9,5,8};			//Value of the items above
+int best=0; 
+
+void knap(int tot, int i, int cost)
+{ 
+
+	//NOTE : WE HAVE TO PUT REJECT CASE AFTER ACCEPT AS OTHERWISE LAST VALUE WON'T COMPUTE, i.e, 
+			//for weight[0], wont be included
+
+	if(tot<0||i<-1)
+	return;
+
+
+
+
+	//NOTE: it is i=-1 so that i=0 pulls of.. i-1, cost+weight[0];
+	if(i==-1 || tot==0 ) //Even if total is not 0, and last item then also we see the result
+	{ if(cost>best)
+		best=cost;
+
+		return;
+	}	
+
+
+
+//NOTE: The order is important
+
+	knap(tot,i-1,cost);					//Case2: Excluding element, Item not included
+
+	knap(tot-weight[i],i-1,cost+val[i]);	//Case1: Including only once, Item included
+
+//Not like coin change where each item can be taken more than once, IF item chosen, then also index -1.. In coin: index remains.
+
+
+	return;
+
+}
+
+int main()
+{ 	clock_t t;
+    t = clock();
+
+	int total;
+	cout<<"Enter the total weight the thief can carry: ";
+	cin>>total;
+
+	int n=sizeof(weight)/sizeof(weight[0]); //Size of weight array, as we have to subtract this from total weight
+	if(n-1<=0)
+	{ cout<<"No items available";
+	return 0;
+    }
+
+	knap(total,n-1,0);
+
+	cout<<"The maximum value of things he can carry is :"<<best;
+
+
+
+	t=clock()-t;
+	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+
+    printf("\nTook %f seconds to execute \n", time_taken);
+	return 0;
+}