Cerinta completa

Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created. To create the sum, use any element of your array zero or more times.

For example, if and your target sum is , you might select or . In this case, you can arrive at exactly the target.

Function Description

Complete the unboundedKnapsack function in the editor below. It must return an integer that represents the sum nearest to without exceeding the target value.

unboundedKnapsack has the following parameter(s):

  • k: an integer
  • arr: an array of integers

Input Format

The first line contains an integer , the number of test cases.

Each of the next pairs of lines are as follows:
– The first line contains two integers and , the length of and the target sum.
– The second line contains space separated integers .

Constraints


Output Format

Print the maximum sum for each test case which is as near as possible, but not exceeding, to the target sum on a separate line.

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;
import java.lang.*;

public class Solution {
  public static Hashtable<Integer, Integer> cache;
  public static HashSet<Integer> arr;
  public static int min;

  public static int solve(int k) {
    if (k < min) { return 0; }
    if (cache.containsKey(k)) { return cache.get(k); }
    int max = Integer.MIN_VALUE;
    Iterator<Integer> it = arr.iterator();
    while (it.hasNext()) {
      int current = it.next();
      if (current <= k) {
        max = Math.max(max, solve(k - current) + current);
      }
    }

    cache.put(k, max);

    return max;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    for (int i = 0; i < t; i++) {
      min = Integer.MAX_VALUE;
      cache = new Hashtable<Integer, Integer>();
      int n = sc.nextInt();
      int k = sc.nextInt();
      arr = new HashSet<Integer>();
      for (int j = 0; j < n; j++) {
        int current = sc.nextInt();
        arr.add(current);
        min = Math.min(min, current);
      }
      System.out.println(solve(k));
    }
  }
}

Scor obtinut: 1.0

Submission ID: 464604799

Link challenge: https://www.hackerrank.com/challenges/unbounded-knapsack/problem

Knapsack