CareerCup

This is the classical unbounded knapsack problem.

O(N^2) time O(N) space.

int knapsack(int length, const vector<int>& V, const vector<int>& L)
{
	vector<int> M(length+1,0);
	for(int len=1; len<=length; len++) {
		for(int j=0; j<L.size(); j++) {
			if( L[j] <= len ) 
				M[len] = max(M[len], M[len-L[j]] + V[j]);
		}
	}
	return M[length];
}

array v is the values of rods with length as index i.e. v[2] is the value of rod of length 2.
b is the array of max benefit of rod of length as index. b[2] is the maximum benifit we can get from rod of length 2.

// int[] v = {1,5,8,9}; // Array of values for each size
// int[] b = new int[val.length];
b[0] will be 0 as there is no value for no rod. b[1] is v[1] as we can not have any more combinations.

public int getMaxBenifit(int n) {
	int sum = 0;
	int val = 0;
	b[0] = 0;
	b[1] = v[1];
	for(int k = 2; k<n; k++)
	{
		for(int i = i; i <= k ; i++) {
			val = v[i] + b[k-i];
			if(val > sum)
				sum = val;
		}
		b[k] = sum;
	}
}

space complexity = O ( N )
running complexity = O ( N^2 )

public static int rod_cutting(int V[], int N){
		int B[] = new int[N+1];
		B[0] = 0;
		
		for(int i = 1; i <= N ; i++){
			int max =  V[i];
			for(int j = 1; j < i; j++){
				int current = V[j] + B[i-j];
				max = Math.max(max,current);
			}
			B[i] = max;
		}
	return B[N];		
	}