-----------------------------------

MysticVegeta

Fri Apr 21, 2006 9:15 am


Yet another problem with DP

-----------------------------------

Hey guys, I am working on this problem, where S = sum. The elements of array "arr" tell us the value of each element in integers. And I have to find the minimum # of elements needed from the array "arr" to make the sum S, I dont know where my DP is wrong. Please help me out, the answer is supposed to be 21. It works with some of the other cases but not all. 
Java Solution:

import java.io.*;
import java.util.*;
public class Problem
{
    public static void main (String [] Args) throws IOException
    {
			int arrayLength = 21;
		
			int S = 123;
			
			int [] arr = {7,7,7,7,8,8,8,2,2,2,2,2,2,2,2,2,5,12,12,12,12};
			
			Arrays.sort(arr);
			
			int [] Min = new int [S+1];
			
			Arrays.fill(Min,1000);

			Min[0] = 0;
			
			for (int k = 1; k