Solve using recursion only First integer of input refers to the total weight the
ID: 3553214 • Letter: S
Question
Solve using recursion only
First integer of input refers to the total weight the ship can carry. Second integer refers to the number of cargo present and the rest of the integers represents the individual weight of the cargo
For output, all integers except the last are the individual weight of the cargo in order of their previous input and the final integer represents the total weight
Input 99 7 50 40 2 3 8 13 24
Output 50 40 8 98
Input 62 7 50 40 2 3 8 13 24
Output 50 3 8 61
Input 23 6 8 12 13 5 6 4
Output 8 5 6 4 23
Explanation / Answer
Foramtted code at : http://ideone.com/QevlOv
---------------------------------------------------------------------------
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main {
// Recursive method that returns true iff a subset of values in
// numbers[0..size-1] sums to target.
public static int[] res = new int[10000] ;
public static int pos = 0 ;
public static boolean subsetsumrec(int[] numbers, int target, int start , int size) {
// Nothing sums to 0.
if (target == 0)
return true;
// Can't some to anything else without some numbers.
if (start == size )
return false;
// Either we don't take the number stored at index size-1...or we do.
if(subsetsumrec(numbers, target-numbers[start], start+1,size))
{res[pos++] = numbers[start]; return true; }
else
return subsetsumrec(numbers, target, start+1,size) ;
}
// Returns true iff numbers has a subset of values that adds upto target.
public static int subsetsum(int[] numbers, int target) {
boolean[] answers = new boolean[target+1];
answers[0] = true;
for (int i=1; i<answers.length; i++)
answers[i] = false;
// Consider each item one by one.
for (int i=0; i<numbers.length; i++) {
// Loop through the array backwards, since we don't want to add in
// a single element twice.
for (int sum=target; sum >= numbers[i]; sum--) {
// If we have a way to add to sum-numbers[i], now with numbers[i]
// we can add to sum...
if (answers[sum-numbers[i]])
answers[sum] = true;
}
}
for (int sum=target; sum >= 0; sum--)
if(answers[sum]) return sum ;
// Returns our answer.
return 0;
}
public static void main(String[] args) {
// Just a couple of tests.
Scanner in = new Scanner(System.in);
int target = in.nextInt();
int total = in.nextInt();
int[] vals = new int[total];
pos = 0 ;
for(int i =0 ; i < total ; i++)
vals[i] = in.nextInt() ;
int num = subsetsum(vals,target);
boolean flag = subsetsumrec(vals,num,0,vals.length);
for(int i = pos-1 ; i >= 0 ; i-- )
System.out.print(res[i] + " " );
System.out.println(num);
}
}