题目描述

A warehouse manager needs to create a shipment to fill a truck. All of the products in the warehouse are in boxes of the same size. each product is packed in some number of units per box. Given the number of boxes the truck can hold, determine the maximum number of units of any mix of products that can be shipped

样例

boxes = [1,2,3]
unitsPerBox = [3,2,1]
truckSize = 3;

shipped is 3 + 2 + 2 = 7

01背包 $O(n*m)$

(本人菜鸡，且OA题目没有标准答案，所以难免出错，有更好的解法或此解法有问题请大佬留言)

C++ 代码

int efficientShippint(vector<int> &boxs, vector<int> &unitsPerBox, int truckSize)
{
    int f[truckSize + 1];
    memset(f, 0, sizeof f);

    for(int i = 0; i < boxs.size(); i++)
    {
        for(int j = truckSize; j >= boxs[i]; j--)
            f[j] = max(f[j], f[j - boxs[i]] + (boxs[i] * unitsPerBox[i]));
    }

    return f[truckSize];
}