106 lines
3.1 KiB
JavaScript
106 lines
3.1 KiB
JavaScript
/**
|
||
* @package: chooseDistance
|
||
* @date: 05.10.2021
|
||
* @time: 08:17
|
||
* @author: Yevhen Odynets <dev@amok.space>
|
||
*/
|
||
|
||
/**
|
||
* Визначаємо суми всіх підмножин з масиву чисел та їх суми згідно параметрів.
|
||
* Функція поверне підмножину відстаней або null.
|
||
*
|
||
* @param t
|
||
* @param k
|
||
* @param ls
|
||
* @returns {null|*[]}
|
||
*/
|
||
function chooseDistance (t, k, ls) {
|
||
|
||
/**
|
||
* Перевіряємо чи коретно передані відстані у масиві 'ls' і чи є він власне масивом
|
||
*/
|
||
if (Array.isArray(ls)) {
|
||
if (ls.map(el => (Number.isInteger(el) && el >= 0)).includes(false)) {
|
||
return null
|
||
}
|
||
} else {
|
||
return null
|
||
}
|
||
|
||
const data = {} //результуючий набір
|
||
const n = ls.length //довжина масиву
|
||
const total = 1 << n //Загальна кількість підмножин
|
||
|
||
/** Перевіряємо змінні на валідність */
|
||
if (!Number.isInteger(k) || k < 1) {
|
||
return null
|
||
}
|
||
|
||
if (n < k) {
|
||
return null
|
||
}
|
||
|
||
if (!Number.isInteger(t) || t < 0) {
|
||
return null
|
||
}
|
||
|
||
/**
|
||
* Перевіряємо всі числа від 0 до 2^n - 1
|
||
*/
|
||
for (let i = 0; i < total; i++) {
|
||
let sum = 0
|
||
const subset = []
|
||
|
||
/**
|
||
* Обераємо елементи до підмножин
|
||
*/
|
||
for (let j = 0; j < n; j++) {
|
||
if ((i & (1 << j)) !== 0) {
|
||
sum += ls[j]
|
||
subset.push(ls[j])
|
||
/**
|
||
* Відсікаємо зайве
|
||
*/
|
||
if (sum <= t && subset.length === k) {
|
||
data[sum] = subset.slice(0, k) //не певен, що це найкращий варіант)))
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* Визначаємо найбільше значкення ключа, і по ньому повертаємо набір відсттаней згідно умов задачі
|
||
*/
|
||
const maxKeySum = Math.max.apply(null, Object.keys(data))
|
||
return data[maxKeySum] ?? null
|
||
}
|
||
|
||
const results = [
|
||
chooseDistance(174, 3, [51, 56, 58, 59, 61]), // [ 56, 58, 59 ]
|
||
chooseDistance(163, 3, [50]), // null
|
||
|
||
chooseDistance(47, 'three', [51, 56, 58, 59, 61]), // null
|
||
chooseDistance( null, 3, [51, 56, 58, 59, 61]), // null
|
||
chooseDistance( 175, 3, [51, 56, 0, 59, 61]), // [ 51, 59, 61 ]
|
||
chooseDistance( 175, 3, [51, 56, '0', 59, 61]), // null
|
||
|
||
chooseDistance(50, 1, [51, 56, 58, 59, 61]), // null
|
||
chooseDistance(51, 1, [51, 56, 58, 59, 61]), // [ 51 ]
|
||
|
||
chooseDistance(119, 2, [51, 56, 58, 59, 61]), // [ 58, 61 ]
|
||
|
||
chooseDistance(223, 4, [51, 56, 58, 59, 61]), // null
|
||
chooseDistance(224, 4, [51, 56, 58, 59, 61]), // [ 51, 56, 58, 59 ]
|
||
chooseDistance(256, 4, [51, 56, 58, 59, 61]), // [ 56, 58, 59, 61 ]
|
||
|
||
chooseDistance(285, 5, [51, 56, 58, 59, 61]), // [ 51, 56, 58, 59, 61 ] - max sum of the array is 285
|
||
chooseDistance(284, 5, [51, 56, 58, 59, 61]), // null
|
||
|
||
chooseDistance(285, 6, [51, 56, 58, 59, 61]), // null
|
||
|
||
]
|
||
|
||
console.log(results[0]) // Dylan's request ([ 56, 58, 59 ])
|
||
|
||
console.log(results)
|