for programming interview-part7

today we shall discuss a problem related to finding max sum in array such that max sum elements are not adjacent to each other.ie if the array element are given as
1,3,5,10=>13
1,7,9,21=>22
ans

#include < iostream >
using namespace std;
void FindMaxSum(int buf[],int cnt)
{
int incl = 0; // max sequence including the previous item
int excl = 0; // max sequence excluding the previous item
int excl_new=0;

for (int i = 0; i < cnt; i++)
{
// current max excluding i
if (incl > excl)
{excl_new = incl;
cout << "if\t" << excl_new << endl;
}
else
{
excl_new = excl;
cout << "else\t" << excl_new << endl;
}

// current max including i
incl = excl + buf[i];
excl = excl_new;


}
cout << "\nmax sum = " << ((incl > excl)? incl : excl) << endl;
}
int main()
{
int a[5]={3,2,7,10};
FindMaxSum(a,5);
getchar();
return 0;
}

we shall discuss another beautiful problem which is one of my all time favorites the knapsack problem.hope all of u would have studied about this in CLRS.

let W be max weight
let A[] be the array with articles of different weights.
let n be the max number of items

int findprice(int A[],int n)
{
int cost=0;
for(int i=0;i < n;++i)
cost+=max(findprice(A[],n-1),A[i]+findprice(W-A[i],n-1));
return cost;
}

here we can bring various optimization like using dynamic programming like storing in table the values instead of using subsequent rec call