Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- public class Backtracking_zerooneknapsack {
- static boolean isDebugMode = false;
- public static void main(String[] args)
- {
- double capacity_weight = 10;
- Integer[] weight = new Integer[]{2, 3, 2, 5, 3};
- Integer[] val = new Integer[]{40, 50, 100, 95, 30};
- System.out.println("v: ");
- printArray(val);
- System.out.println("w: ");
- printArray(weight);
- Integer finalVal = backtracking(capacity_weight, val, weight);
- System.out.println("result: ");
- System.out.println(finalVal);
- }
- private static Integer backtracking(double capacity_weight, Integer[] vals, Integer[] weights) {
- Integer curWeight = 0;
- Integer curVal = 0;
- Integer curIndex = 0;
- int finalVal = goDownDFS(capacity_weight, vals, weights, curWeight, curVal, curIndex);
- return finalVal;
- }
- private static Integer goDownDFS(double capacity_weight, Integer[] vals, Integer[] weights, Integer curWeight, Integer curVal, Integer curIndex) {
- // ending point
- if ( curWeight > capacity_weight) { // backtracking here
- return -1; // 爆了,所以當作最小價值
- }
- if (curIndex >= vals.length) {
- return curVal;
- }
- // if take
- int ifTakeWeight = curWeight + weights[curIndex];
- int ifTakeVal = curVal + vals[curIndex];
- int ifTakeCurrVal = goDownDFS(capacity_weight, vals, weights, ifTakeWeight, ifTakeVal, curIndex+1);
- // if not take
- int ifNotTakeWeight = curWeight;
- int ifNotTakeVal = curVal;
- int ifNotTakeCUrrVal = goDownDFS(capacity_weight, vals, weights, ifNotTakeWeight, ifNotTakeVal, curIndex+1);
- return Math.max(ifTakeCurrVal, ifNotTakeCUrrVal);
- }
- ///// Util Only below /////
- public static int[][] generateDeepCopy2dAry(int[][] original) {
- if (original == null) {
- return null;
- }
- final int[][] result = new int[original.length][];
- for (int i = 0; i < original.length; i++) {
- result[i] = Arrays.copyOf(original[i], original[i].length);
- // For Java versions prior to Java 6 use the next:
- // System.arraycopy(original[i], 0, result[i], 0, original[i].length);
- }
- return result;
- }
- private static void printArray(Object[] ary){
- for (int i = 0; i < ary.length; i++) {
- System.out.printf("%4d" , ary[i]);
- }
- System.out.println();
- }
- private static void print2DArray(int[][] ary){
- for (int i = 0; i < ary.length; i++) {
- for (int j = 0; j < ary[i].length; j++) {
- System.out.printf("%4d" , ary[i][j]);
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement