鍍金池/ 問(wèn)答/人工智能  HTML/ 雙核處理器并行處理任務(wù)的最短時(shí)間算法?

雙核處理器并行處理任務(wù)的最短時(shí)間算法?

雙核處理器可以并行處理任務(wù),它們的處理速度都為1k/s,每個(gè)任務(wù)以k為單位,如[300, 600, 300, 500, 1000, 700, 300],求一堆任務(wù)的最短時(shí)間算法?

下面是我自己用JavaScript寫的一個(gè)算法,還是有點(diǎn)問(wèn)題,問(wèn)下有好的方法嗎?

    let arr = [300, 600, 300, 500, 1000, 700, 300];
    let left = [];
    let right = [];
    let lefts = 0;
    let rights = 0;
    let flag = true; // 第一次累加最大值 第二次累加最小值 平分兩組任務(wù)
    function task(arr) {
        // 平分兩組任務(wù)
        let newArr = arr.sort((a, b) => b - a);
        if (flag) {
            left.push(newArr[0]);
            right.push(newArr[1]);
            newArr = newArr.slice(2);
        } else {
            left.push(newArr[newArr.length - 1]);
            right.push(newArr[newArr.length - 2]);
            newArr = newArr.slice(0, newArr.length - 2);
        }
        // 開關(guān)循環(huán) 第一次加最大值 第二次加最小值 依次累加
        flag = !flag; 
        // 兩組任務(wù)分別之和
        lefts = left.reduce((a, b) => a + b);
        rights = right.reduce((a, b) => a + b);
        // 只剩下一個(gè)任務(wù)或0個(gè)任務(wù)時(shí),最終結(jié)果計(jì)算
        if (newArr.length <= 1) {
            if (newArr.length == 1) {
                if ((lefts - rights) > newArr[0]) {
                    return lefts;
                } else {
                    right.push(newArr[0]);
                    rights = right.reduce((a, b) => a + b);
                    return rights;
                }
            } else {
                if (lefts < rights) {
                    return rights;
                } else {
                    return lefts;
                }
            }
        }
        // 遞歸調(diào)用實(shí)現(xiàn)循環(huán)
        return task(newArr);
    };
    console.log("最短輸出時(shí)間為:" + task(arr) + 's');
回答
編輯回答
情皺

是NP-hard問(wèn)題。近似算法參見partition problem。

2017年12月18日 23:50