Knapsack.java

import java.util.*;
class Result {
    // declare the member field
 private int[] myBag;
 private int length;
    // declare the constructor
 public Result(int[] bag){
  myBag = bag;
  length = myBag.length;
 }
 /**
  * solve   : to count the number of sets of items satisfying the criteria.
  *          (the total weight of all items in a set should not exceed the capacity of the sack)
  *  Pre-condition   : myBag exists
  *  Post-condition  : returns number of solutions given the capacity
  */
 // you should determine the recurrence state(parameters) yourself.
 public int solve(int remWeight, int currentCount) {
  // implementation
  int output;
  int topWeight, nextRemWeight;
  if (currentCount >= length || remWeight == 0){
   output = 1;
  } else{
   topWeight = myBag[currentCount];
   if (topWeight > remWeight){
    output = solve(remWeight, currentCount + 1);
   } else {
    nextRemWeight = remWeight - topWeight;
    output = solve(remWeight, currentCount + 1) + solve(nextRemWeight, currentCount + 1);
   }
  }
  return output;
 }
}
class Knapsack {
 public static void main(String[] args) {
  // declare the necessary variables
  int numberOfItems, capacity, itemWeight;
  int[] myBag;
  Result myResult;
  // declare a Scanner object to read input
  Scanner myScanner = new Scanner(System.in);
  // read input and process them accordingly
  numberOfItems = myScanner.nextInt();
  myBag = new int[numberOfItems];
  capacity = myScanner.nextInt();
  for (int i = 0; i < numberOfItems; i++){
    itemWeight = myScanner.nextInt();
    myBag[i] = itemWeight;
  }
  myResult = new Result(myBag);
  System.out.println(myResult.solve(capacity, 0));
 }
}