import java.util.*;
public class Recurse
{
static Random seed = new Random();
public static void main(String[] args)
{
int limit = 16;
int size = 10;
int maxVal = 25;
for(int j = 0; j < 5; j++) {
int[] n = getArray(limit, size);
System.out.printf("n = %s maxVal = %d%n",
Arrays.toString(n), maxVal);
System.out.printf(" getMax() = %d%n", getMax(n, maxVal, 0, 0));
System.out.printf(" getSum() = %d%n", getSum(n, maxVal));
System.out.printf("maxPack() = %d%n", maxPack(n, 0, size-1, maxVal));
System.out.println("----------");
}
}
private static int getMax(int[] array, int maxValue, int index, int value) {
if(value + array[index] <= maxValue)
value += array[index];
else
return value;
if(index == array.length-1)
return value;
return getMax(array, maxValue, index+1, value);
}
private static int getSum(int[] array, int goalWeight) {
int weight = 0;
for(int j = 0; j < array.length; j++) {
if(weight + array[j] > goalWeight)
break;
weight += array[j];
}
return weight;
}
private static int maxPack(int[] A, int first, int last, int goalWeight)
{
int maxWeight = 0;
int with = 0;
int without = 0;
if(goalWeight <= 0) return 0;
if(first == last){
if(A[first] <= goalWeight) maxWeight += A[first];
return maxWeight;
}
else{
if (A[first] <= goalWeight) {
with += A[first];
with += maxPack(A, first + 1, last, (goalWeight - A[first]));
}
without += maxPack(A, first + 1, last, goalWeight);
if(with < goalWeight || without < goalWeight){
if(without < goalWeight){
if(with > without) {
maxWeight += with;
return maxWeight;
}
else {
maxWeight += without;
return maxWeight;
}
}
else{
assert(with < goalWeight);
maxWeight += with;
return maxWeight;
}
}
return 0;
}
}
private static int[] getArray(int limit, int size) {
int[] n = new int[size];
Arrays.fill(n, limit+1);
int count = 0;
while(count < size) {
int candidate = seed.nextInt(limit+1);
if(!contains(n, candidate))
n[count++] = candidate;
}
return n;
}
private static boolean contains(int[] array, int target) {
for(int j = 0; j < array.length; j++) {
if(array[j] == target)
return true;
}
return false;
}
}