Famous problems

ShivanshJ · Mar 20, 2017 · ef2aab6 · ef2aab6
1 parent 831ea48
commit ef2aab6
Show file tree

Hide file tree

Showing 2 changed files with 68 additions and 12 deletions.
diff --git a/Knapsack (Thief)_Dynamic.cpp b/Knapsack (Thief)_Dynamic.cpp
@@ -0,0 +1,66 @@
+#include<iostream>
+#include<string.h>
+#include<stdio.h>
+#include<math.h>
+#include<time.h>
+using namespace std;
+
+
+//.......................................Look at Naive for all comments
+//NOTE: Instead of global variable best, max() is used
+
+
+#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 save[40][5]={0}; 
+//Save array, here it is taken in the form of 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)
+{ 	//Return statements
+	if(tot<0||i<-1)
+	return 0;
+
+	if(save[tot][i]>0 )
+		return save[tot][i];
+	//Accept
+	if(i==-1 || tot==0 ) 	
+		return cost; //Cost is calculated for a particular sub-problem as shown in recursion tree in the link stated
+	//Recursive
+	save[tot][i]=max( knap(tot,i-1,cost) , knap(tot-weight[i], i-1,cost+val[i]) ); 
+
+	return save[tot][i];
+}
+
+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;
+    }
+
+
+
+	cout<<"The maximum value of things he can carry is :"<<knap(total,n-1,0);
+
+	t=clock()-t;
+	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+
+    printf("\nTook %f seconds to execute \n", time_taken);
+	return 0;
+
+}	
diff --git a/Knapsack (Thief)_Naive.cpp b/Knapsack (Thief)_Naive.cpp
@@ -24,9 +24,6 @@ void knap(int tot, int i, int cost)
 	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)
@@ -35,17 +32,12 @@ void knap(int tot, int i, int 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
+	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.
 
-//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;
 
 }
@@ -68,8 +60,6 @@ int main()
 
 	cout<<"The maximum value of things he can carry is :"<<best;
 
-
-
 	t=clock()-t;
 	double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds