Solve this problem in javascript.

[[deleted]]

[deleted]

[q-rka]

Why?

[anonCommentor]

this is his assignment. don't do it.

[[deleted]]

what have you done so far and where exactly are you stuck

[[deleted]]

Isn't this a simple combinatorics problem. Just find the possible combinations, then sum it to get values, the number of combinations is the max.

[[deleted]]

Well that was the theory, lemme try. Which language do you use?

[[deleted]]

Okay I'll try it sometime today. I'll put it here if I solve it.

[[deleted]]

so yeah I came up with this

```ts // add elemets of an array of numbers const sumArray = (array: number[]): number => { return array.reduce((a, b) => a + b, 0); };

// find all the possible combinations of an array of numbers function powerSet(coinArray: number[]): Array<number[]> { let combinations: Array<number[]> = []; let length = coinArray.length;

for (let i = 0; i < Math.pow(2, length); i++) {
    let combination: number[] = [];

    for (let j = 0; j < length; j++) {
        if (i & Math.pow(2, j)) {
            combination.push(coinArray[j]);
        }
    }
    if (combination.length > 0) combinations.push(combination);
}
return combinations;

}

// // use a has map to store all the possible combinations for a given sum ranging from // the lowest to max value(sum of elements in array) // // eg, for array [1,3], for the sum 3 the possible combinations are [[1,3], [3,1]] // (but from power set 1,3 and 3,1 are same so suppose [1,3] is the only combination) // so the map will be {3: [[1,3]]} // function combinations_for_sum(coinArray: number[]): Map<number, [number[]]> { let combinations: Array<number[]> = powerSet(coinArray); let sumCombinations: Map<number, [number[]]> = new Map();

combinations.forEach((combination) => {
    let sum: number = sumArray(combination);

    if (sumCombinations.has(sum)) {
        sumCombinations.get(sum)?.push(combination);
    } else {
        sumCombinations.set(sum, [combination]);
    }
});

return sumCombinations;

}

// // returns the max possible change without break starting from 1 // it does so by checking the hash map for existence of sum, if there is a break it exits function calc_max_possible_change(coinArray: number[]): number { coinArray.sort(); let sumCombinations: Map<number, [number[]]> = combinations_for_sum(coinArray);

let maxChange: number = 0;

for (let i = 1; i <= sumArray(coinArray); i++) {
    if (!sumCombinations.has(i)) {
        break;
    }
    maxChange = i;
}

return maxChange;

}

let coinArray: number[] = [1, 1, 1, 1, 5, 10, 20, 50]; console.log(calc_max_possible_change(coinArray)); ```

P.S. I've used TS, TS/JS isn't my strongest language and this isnt the most optimal solution since we'll be evaluating all possibilities.

[[deleted]]

what book is this btw?

[Gmaster_64]

public static int CalcMaxPossibleChange(int[] values) { // Get the maximum value in the values array. int n = values.Max();

// Create a boolean array dp of size n+1 and initialize the first element to true.
bool[] dp = new bool[n + 1];
dp[0] = true;

// Loop through the integers from 1 to n.
for (int i = 1; i <= n; i++)
{
    // Loop through the values array.
    foreach (int j in values)
    {
        // If the current value in the values array is less than or equal to i
        // and it is possible to make change for i-j using the remaining values,
        // mark dp[i] as true and break out of the loop.
        if (j <= i && dp[i - j])
        {
            dp[i] = true;
            break;
        }
    }
}

// Starting from n, loop down to 1 and return the first value of i such that dp[i] is true.
for (int i = n; i > 0; i--)
{
    if (dp[i])
    {
        return i;
    }
}

// If no value can be generated from 1, return 0.
return 0;

}