# 求js或c写法及思路，需求如下：

mikalshaol 2017年03月20日提问
0

## 2个回答

0

``````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;``````

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;
}``````