最优分配问题，算法求解

Question

​
有3种不同的货物a,b,c， 需要4种类型的车运输w,x,y,z， 每种货物运输完所需的车辆数如下表：
a需要w车50辆，x车40辆，y车20辆，z车10辆
b需要w车30辆，x车20辆，y车16辆，z车8辆
c需要w车30辆，x车20辆，y车12辆，z车6辆
每种货物只能用一种车型运行，现在共有w 型车100辆  ，x型车50辆 ， y型车50辆 ， z型车16辆 ，问怎么分配车辆，才能派出的车数最少

​

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
为了解决这个问题，我们可以使用贪心算法。首先，我们将每种货物分配到车辆，然后在每一轮中选择当前最优的分配方案。

1. 初始化变量：

a(需要运输的货物):3,4,5

b(需要运输的货物):2,3,4

c(需要运输的货物):1,2,3

车辆(可以运输的货物):w,x,y,z

车辆数：100,50,50,16

1. 第一步：选择货物a需要的车辆数最少的车型。在这里，货物a需要运输3个单位，所以我们需要选择可以运输3个单位的车型。最便宜的车型是x和y,但我们需要确保所有货物都能被运输完。因此，我们选择x。

2. 第二步：为货物a选择对应的车辆。在这个例子中，我们需要为货物a选择50辆x型车。

3. 第三步：更新剩余货物的信息。现在我们需要为货物b和c选择车辆。货物b需要运输2个单位，所以我们可以选择z型车。货物c需要运输1个单位，所以我们可以选择w或y型车。但是我们需要确保所有货物都能被运输完，所以我们选择w型车。

4. 第四步：为剩余货物选择对应的车辆。在这个例子中，我们需要为剩余的货物选择50辆w型车。

5. 重复步骤2-5,直到所有的货物都被运输完。在这个例子中，我们只需要进行一次操作，因为所有的货物都已经分配完了。

最终得到的车辆数为：$50+50+16$ =116辆。这是最少的车辆数，因为我们始终在选择可以运输更多货物的车型。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int a[] = {3, 4, 5};
    int b[] = {2, 3, 4};
    int c[] = {1, 2, 3};
    int w = 100, x = 50, y = 50, z = 16;

    vector<int> vehicles = {w, x, y, z};
    sort(vehicles.begin(), vehicles.end());

    for (int i = 0; i < 3; i++) {
        int min_vehicle = -1;
        for (int j = 0; j < 4; j++) {
            if (a[i] <= vehicles[j]) {
                min_vehicle = j;
            }
        }
        if (min_vehicle == -1) {
            cout << "无法分配货物" << endl;
            return 0;
        }
        vehicles[min_vehicle] -= a[i];
    }

    for (int i = 0; i < 3; i++) {
        int min_vehicle = -1;
        for (int j = 0; j < 4; j++) {
            if (b[i] <= vehicles[j]) {
                min_vehicle = j;
            }
        }
        if (min_vehicle == -1) {
            cout << "无法分配货物" << endl;
            return 0;
        }
        vehicles[min_vehicle] -= b[i];
    }

    for (int i = 0; i < 3; i++) {
        int min_vehicle = -1;
        for (int j = 0; j < 4; j++) {
            if (c[i] <= vehicles[j]) {
                min_vehicle = j;
            }
        }
        if (min_vehicle == -1) {
            cout << "无法分配货物" << endl;
            return 0;
        }
        vehicles[min_vehicle] -= c[i];
    }

    cout << "最少需要车辆数：" << accumulate(vehicles.begin(), vehicles.end(), 0) << endl;

    return 0;
}

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢