-
Notifications
You must be signed in to change notification settings - Fork 0
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
Showing
3 changed files
with
172 additions
and
0 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,46 @@ | ||
#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 mon[]={5,2,1,10,7,3}; | ||
int best=0; | ||
|
||
int mx(int a, int b) | ||
{ return a>b?a:b ; | ||
} | ||
|
||
void gold(int n, int sum) | ||
{ | ||
if(n<-2) | ||
return; | ||
|
||
|
||
//Base cases | ||
//Note: n==-2, since last element will be added only when gold(0-2,sum+mon[0]) | ||
if(n==-2 || n==-1 ) | ||
{ if(best < sum) | ||
best=sum; | ||
return; | ||
} | ||
|
||
gold(n-2,sum+mon[n]); //Case1: Include, then go down by two, cuz no adjacent | ||
gold(n-1,sum); //Case2: Exclude, then shift by 1; | ||
|
||
|
||
return; | ||
} | ||
|
||
int main() | ||
{ int n=sizeof(mon)/sizeof(mon[0]); | ||
gold(n-1,0); | ||
cout<<best; | ||
return 0; | ||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,62 @@ | ||
#include <stdio.h> | ||
#include <math.h> | ||
#include <stdlib.h> | ||
#include<iostream> | ||
using namespace std; | ||
|
||
#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++) | ||
#define RF(i,a,b) for(int i= (int)(a) ; i > (int)(b) ; i--) | ||
|
||
|
||
//Non CONTIGUOUS | ||
// to make it non-c... we take sum from S[i-2] + current position or we take it for series ending at S[i-1] | ||
|
||
//........................extra note: for recursion, the function are would be: | ||
// int func( int a[], sum, int i) | ||
// .. | ||
// func(a, sum + a[i], i-2) | ||
// func(a, sum, i-1) | ||
|
||
|
||
int mx(int a , int b) | ||
{ a>b?cout<<a:cout<<b; | ||
cout<<endl; | ||
|
||
return a>b?a:b; | ||
|
||
} | ||
|
||
|
||
// reasoning at: http://code-em-up.blogspot.in/2012/07/question-given-unsorted-array-of.html | ||
|
||
void sum(int a[10], int n) | ||
{ | ||
|
||
|
||
int sol[10]; //New matrix memoized version | ||
|
||
sol[0]=a[0]; | ||
sol[1]=a[1]; | ||
|
||
F(i,2,n) | ||
sol[i] = mx( (sol[i-2] + a[i]) , sol[i-1] ); | ||
|
||
int res=sol[0]; | ||
|
||
F(j,1,n) | ||
if(res<sol[j]) | ||
res=sol[j]; | ||
|
||
cout<<"Final greatest sum in non- contiguous subarray is: "<<res; | ||
|
||
} | ||
|
||
|
||
int main() | ||
{ int a[10]= {-11,4,-2,8,-10,4,-3,4,3}; | ||
|
||
int n=sizeof(a)/sizeof(a[0]); | ||
|
||
sum(a,n); | ||
|
||
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,64 @@ | ||
#include <stdio.h> | ||
#include <math.h> | ||
#include <stdlib.h> | ||
#include<iostream> | ||
using namespace std; | ||
|
||
#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++) | ||
#define RF(i,a,b) for(int i= (int)(a) ; i > (int)(b) ; i--) | ||
|
||
|
||
//Contiguous sum maximum; | ||
// (x,x,x,x) <- S[i] considering is better then , (x,x,x)<-S[i-1] + a[i] .... Comparing this new one with old | ||
// Thus, S[i]=max(S[i-1] + a[i] ,a[i]) | ||
|
||
//........................extra note: for recursion, the function are would be: | ||
// int func( int a[], sum, int i) | ||
// .. | ||
// func(a, sum + a[i], i-1) | ||
// func(a, a[i], i-1) | ||
|
||
|
||
int mx(int a , int b) | ||
{ a>b?cout<<a:cout<<b; | ||
cout<<endl; | ||
|
||
return a>b?a:b; | ||
|
||
} | ||
|
||
//NOTE : This memoized just makes sure it memorises the previousl computed value of sum for each | ||
//Fine reasoning at: http://blog.saadtaame.org/2016/06/the-maximum-contiguous-subarray-problem.html | ||
|
||
//IMP : https://people.cs.clemson.edu/~bcdean/dp_practice/ | ||
|
||
void sum(int a[10], int n) | ||
{ | ||
|
||
|
||
int sol[10]; //New matrix memoized version | ||
|
||
sol[0]=a[0]; | ||
|
||
F(i,1,n) | ||
sol[i] = mx( (sol[i-1] + a[i]) , a[i] ); | ||
|
||
int res=sol[0]; | ||
|
||
F(j,1,n) | ||
if(res<sol[j]) | ||
res=sol[j]; | ||
|
||
cout<<"Final greatest sum in contiguous subarray is: "<<res; | ||
|
||
} | ||
|
||
|
||
int main() | ||
{ int a[10]= {-11,4,-2,8,-10,4,-3,4,3}; | ||
|
||
int n=sizeof(a)/sizeof(a[0]); | ||
|
||
sum(a,n); | ||
|
||
} |