HackerRank: Knapsnack
You are given an integer k as well as n, not necessarily distinct, integers. Define the MULTSUM of a multiset (defined below) to be the sum of all integers in the multiset. Then, for all multisets of the n integers, where one can insert a number more than once, you want to find one (or more in case of a tie) so that he MULTSUM is closest to, but less than or equal to k. Once you find this (or these, in case of a tie) output its MULTSUM.
Note: We define a multiset of the n integers as a set of numbers consisting of some, but not necessarily all, of the n numbers. Also note that one integer can be added to the multiset
You are given an integer k as well as n, not necessarily distinct, integers. Define the MULTSUM of a multiset (defined below) to be the sum of all integers in the multiset. Then, for all multisets of the n integers, where one can insert a number more than once, you want to find one (or more in case of a tie) so that he MULTSUM is closest to, but less than or equal to k. Once you find this (or these, in case of a tie) output its MULTSUM.
Note: We define a multiset of the n integers as a set of numbers consisting of some, but not necessarily all, of the n numbers. Also note that one integer can be added to the multiset
private static int getMultSum(HashSet<Integer> map, int k) {
Iterator<Integer> it = map.iterator();
boolean[] sum = new boolean[k + 1];
Arrays.fill(sum, false);
sum[0] = true;
int a = 0;
for (int i = 0; i <= k; i++) {
if (sum[i] == true) {
it = map.iterator();
while (it.hasNext()) {
a = it.next();
if ((i + a) <= k) // i+a=k break outer loop
sum[i + a] = true;
}
}
}
for(int i=k;i>=0;i--){
if(sum[i] == true){
return i;
}
}
return 0;
}
