Advertisement
Josif_tepe

Untitled

May 12th, 2022
627
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.09 KB | None
  1. import java.util.Collection;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class MAin {
  6.     private static int n;
  7.     private static int[] niza;
  8.     private static int[] dp;
  9.     static int rec(int x) {
  10.         if(x == 0) {
  11.             return 0;
  12.         }
  13.         if(dp[x] != -1) {
  14.             return dp[x];
  15.         }
  16.         int result = (int) 2e9;
  17.         for(int i = 0; i < n; i++) {
  18.             if(x - niza[i] >= 0) {
  19.                 result = Math.min(result, rec(x - niza[i]) + 1);
  20.             }
  21.         }
  22.         dp[x] = result;
  23.         return result;
  24.     }
  25.     public static void main(String[] args) {
  26.         Scanner sc = new Scanner(System.in);
  27.         n = sc.nextInt();
  28.         niza = new int[n];
  29.         for(int i = 0; i < n; i++) {
  30.             niza[i] = sc.nextInt();
  31.         }
  32.         int suma = sc.nextInt();
  33.         dp = new int[suma + 1];
  34.         for(int i = 0; i <= suma; i++) {
  35.             dp[i] = -1; // ova ni kazuva deka ovaa rekurzija ne e presmetana
  36.         }
  37.         System.out.println(rec(suma));
  38.     }
  39.  
  40. }
  41. // 50- 10 - 20 = 20
  42. // 60 + 100 +
Advertisement
RAW Paste Data Copied
Advertisement