算法问题：鸡块有 7/13/29 三种规格，老板让你买 n 块，如何计算是否可行

Question

问题：在一个平行宇宙中，麦当劳的麦乐鸡块分为 7 块装、13 块装和 29 块装。有一天，你的老板让你出去购买正好为 n 块(0 < n <= 10000)的麦乐鸡块回来，请提供一个算法判断是否可行。

说明：除了三重循环的解法，有没有效率更高一点的方法。求大佬指点。

Answer 1

function countAll(i, j, k, total) {
    if ((i * 7 + j * 13 + 29 * k) > total) {
        return false;
    }
    if (total === 7 || total === 13 || total === 29) {
        return true;
    }
    if (isVoid(i, j, k, total)) {
        return true;
    } else {
        return countAll(i, j, k + 1 , total) || countAll(i , j + 1, k , total) || countAll(i + 1, j , k , total) ||  false;
    }
}

function isVoid(i, j, k, total) {
    let value = i * 7 + j * 13 + 29 * k;
    if (total % value == 0 && value !== 0) {
        console.log(i , j  , k);
        return true;
    }
    return false;
}
var res = countAll(0, 0 , 0 ,9892);
console.log(res);

递归实现

Answer 2

取巧的一个思路，反正 n块(0< n <= 10000)

1. 直接拿到 0-10000 里 7，13，29 所有可能构成的取值，建立哈希表，结束了
2. 效率肯定很高

Answer 3

const checkNuggets = (nuggets) => {
    let temp = []
    temp[7] = true
    temp[13]-= true
    temp[29] = true
    for (let i = 7; i < nuggets; i+= 1) {
        if (temp[i]) {
            temp[i + 7] = true
            temp[i + 13] = true
            temp[i + 29] = true
        } else continue
    }
    return !!temp[nuggets]
}

console.log(checkNuggets(25)) // false
console.log(checkNuggets(26)) // true
console.log(checkNuggets(27)) // true
console.log(checkNuggets(28)) // true
console.log(checkNuggets(29)) // true
console.log(checkNuggets(30)) // false