# ITSA C_CH11

Jun 3rd, 2020
947
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