Please provide java code or formal algorithm pseudo code with explanation. Expla

Question

Please provide java code or formal algorithm pseudo code with explanation. Explanation is important

Problem 3: (5 2 points) Design an algorithm that takes an array of positive integers A of length n and a positive integer T as an input and finds the largest N such that N can be written as a sum of some elements of A and returns such a representation of N The complexity of the algorithms has to be 0(nT). For example, for A 3,7,10 and T 19, the output is 17 - 7+10, because we can make 17 out of elements of A (7+10) but we cannot make 18 or 19. So the largest N

Explanation / Answer

/////////////////////////////////////////////JAVA CODE//////////////////////////////////////////////////////////////////////////////////

class Main
{

// A utility function that returns maximum of two integers
static int max(int a, int b) { return (a > b)? a : b; }
  
// Returns the maximum value that is less than T
static int Main(int T, int A[], int n)
{
// Base Case as when A is empty or T is 0
if (n == 0 || T<= 0)
return 0;
  
// If value of the nth item is more than T, then
// this item cannot be included in the optimal solution
if (A[n-1] > T)
return Main(T, A, n-1);
  
// Otherwise Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( A[n-1] + Main(T-A[n-1], A, n-1),
Main(T, A, n-1)
);
}


// Driver program to test above function
public static void main(String args[])
{
  
int wt[] = new int[]{3, 7, 10};
int T = 19;
int n = wt.length;
System.out.println(Main(T, wt, n));
}
}

///////////////////////////////////////////////////////EXPLANATION///////////////////////////////////////////////////////////////////

To consider all subsets of elements, there can be two cases for every elements:

(1) the item is included in the solution subset, or

(2) not included in the solution set.

Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and T value (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus value of the nth item (including nth item).

If value of nth item is greater than T, then the nth item cannot be included and case 1 is the only possibility.

/////////////////////////////////////////////////Dynamic Programming ////////////////////////////////////////////////////////////

class Main

{

// A utility function that returns maximum of two integers

static int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value less than T

static int Main(int T, int A[], int n)

{

int i, w;

int K[][] = new int[n+1][T+1];

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++)

{

for (w = 0; w <= T; w++)

{

if (i==0 || w==0)

K[i][w] = 0;

else if (A[i-1] <= w)

K[i][w] = max(A[i-1] + K[i-1][w-A[i-1]], K[i-1][w]);

else

K[i][w] = K[i-1][w];

}

}

return K[n][T];

}

// Driver program to test above function

public static void main(String args[])

{

int A[] = new int[]{10, 20, 30};

int T = 50;

int n = A.length;

System.out.println(Main(T, A, n));

}

}

//////////////////////////////////////////////////////Time Complexity /////////////////////////////////////////////////////////////////////

Time Complexity: O(nT) where n is the number of items and W is the capacity of knapsack.

since this program we are filling n*T matrix in bottom up manner so its time comlexity will be

Number of line * T*n = Const*n*T

T = O(nT)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.