SHARE
TWEET

ITSA C_CH11

AcerYue Jun 3rd, 2020 791 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static Scanner sc = new Scanner(System.in);
  5.     static int MAX, totalWeight, n, sol = 0;
  6.     static Map<Integer, Integer> weight = new HashMap<>();
  7.     static List<Integer> solution = new ArrayList<>();
  8.     static Map<Integer, List<Integer>> Solution = new HashMap<>();
  9.     public static void main(String args[]) {
  10.         String[] input = sc.nextLine().split(",");
  11.         totalWeight = Integer.parseInt(input[0]);
  12.         MAX = Integer.parseInt(input[1]);
  13.         n = Integer.parseInt(input[2]);
  14.         for(int i = 3; i < 3 + n; i++){
  15.             weight.put(i - 3, Integer.parseInt(input[i]));
  16.         }
  17.         backtracking(1, totalWeight);
  18.         System.out.println(Solution.get(1));
  19.     }
  20.     public static void backtracking(int taked, int weighted){
  21.         if(taked == MAX){
  22.             if(weighted == 0)
  23.                 Solution.put(sol++, solution);
  24.             return;
  25.         }
  26.         for(int i = 0; i < n; i++){
  27.             if(weight.get(i) == null)
  28.                 continue;
  29.             int newWeight = weighted - weight.get(i);
  30.             if(newWeight >= 0){
  31.                 solution.add(i);
  32.                 int value = weight.get(i);
  33.                 weight.remove(i);
  34.                 backtracking(taked + 1, newWeight);
  35.                 weight.put(i, value);
  36.                 solution.remove(solution.size() - 1);
  37.             }
  38.         }
  39.     }
  40. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top