0

现需转运若干个体积<=2000的物料,转运装备体积同样为2000,若任意两个及以上物料体积之和<=2000,则可用一个转运装备,其余任意两个物料体积和>2000,则各自都需要单独装运,求所需最少转运装备数量

2个回答

0

刚刚看了C语言的实现得到启发,写一个js版本,@ACb0y

let arr = [2, 1999, 5, 6, 77, 1666, 455, 3333, 1999, 2222, 4444, 5555, 344, 1234, 567, 34];

function countTotal(arr) {
    arr = arr.sort();
    arrLength = arr.length;
    let count = 0;
    while (arrLength >= 1) {
        let sum = arr[0] + arr[arrLength - 1];
        if (arrLength === 1) {
            count++;
            break;
        }
        if (sum <= 2000) {
            arrLength--;
            arr[arrLength - 1] = sum;
            arr.shift();               
        } else {
            arrLength--;
            arr.pop();
            count++;            
        }
    }
    return count;
}
0
  1. 先对物料进行排序(物料体积从小到大排序)

  2. 使用动态规划算法来计算所需最少转运装备数量

  3. 状态转移方程推到如下:

s[i]表示到第i个物料需要最少的装备数,cur[i]表示当前s[i]所在装备当前的总体积, v[i]表示当前物料体积。

(i == 0) 
    cur[0] = v[0], s[0] = 1;
(i >= 1) 
    cur[i - 1] + v[i] <= 2000 -> cur[i] = cur[i - 1] + v[i], s[i] = s[i - 1]
    cur[i - 1] + v[i] > 2000 -> cur[i] = v[i], s[i] = s[i - 1] + 1;

最后一个s[i]就是答案。

demo代码

#include <stdint.h>
#include <iostream>
using namespace std;

void getCount(int * v, int cnt)
{
    if (NULL == v || cnt <= 0) 
        return;
    
    int * s = new int[cnt];
    int * cur = new int[cnt];
    memset(s, 0x0, cnt);
    memset(cur, 0x0, cut);

    sort(v, v + cnt);
    
    cur[0] = v[0];
    s[0] = 1;
    
    for (int i = 1; i < cnt; ++i)
    {
        if (cur[i - 1] + v[i] <= 2000)
        {
            cur[i] = cur[i - 1] + v[i];
            s[i] = s[i - 1];
        }
        else
        {
            cur[i] = v[i];
            s[i] = s[i - 1] + 1;
        }
    }
        
    cout << s[cnt - 1] << endl;
}

int main()
{
    int v[] = {1, 20, 10, 200, 100, 3430, 2000, 1000, 1000, 1000};
    getCount(v, sizeof(v) / sizeof(int));
    return 0;
}

撰写答案

SegmentFault

一起探索更多未知

下载 App