資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題14：最少裝箱浪費問題(未完)

問題：有 n 個包裝好的商品要裝箱，由 m 個供應商供應各種不同大小的箱子。每個箱子只能裝一個商品，箱子容量減去商品體積為空間的浪費，計算出使用不同供應商的箱子裝箱最少的總空間浪費。若這 m 個供應商的箱子都無法將這些商品完全裝箱，則輸出 -1 。

範例01：輸入商品體積 packages = 2,3,5、供應商 m = 2、箱子容積 boxes = [4,8],[2,8]，代表供應商 0 供應兩種箱子容積分別是 4 , 8、供應商 1 供應容積分別為 2 , 8 的兩種箱子。輸出 6 ，因為使用供應商 0 的箱子裝箱 3 個商品，總空間浪費為(4 - 2) + (4 - 3) + (8 - 5) = 6。

範例02：輸入 packages = 2 , 3 , 5 、 m = 3 、boxes = [1,4], [2,3], [3,4]。輸出 -1 ，因為 3 個供應商的箱子都無法將商品完全裝箱。

範例03：輸入 packages = 3,5,8,12,11,10、m = 3、boxes = [12],[11,9],[10,5,14]。輸出 9 ，因為使用供應商 2 的箱子，總空間浪費為(5 - 3)+(5 - 5)+(10 - 8)+(14 - 12)+ (14 - 11)+ (10 - 10) = 9。

 目前可以處理範例02，但無法處理範例01與範例03：

def packing(p,m,b):

    ok = -1

    name = []

    waste = 0

    wastelist = []

    for i in range(m):

        print(b[i])

        if b[i][len(b[i])-1] > p[len(p)-1]:

            name.append(i)

    print(name,p[len(p)-1])

    if name == []:

        return ok

packages = [int(i) for i in input().split()]

packages.sort(reverse=False)

m = int(input())

boxes =  [[] for _ in range(m)]

for i in range(m):

    boxes[i] = [int(j) for j in input().split()]

    boxes[i].sort(reverse=False)

print(packing(packages,m,boxes))

 

 

 

 

 

 

資料來源：

1.Python 資料結構×演算法 刷題鍛鍊班：234 題帶你突破 Coding 面試的難關

2.LeetCode——1889. 装包裹的最小浪费空间(Minimum Space Wasted From Packaging)[困难]——分析及代码（Java）

題目目錄

01.資料結構-第2章陣列 Array 題目 2.1一維陣列-延伸刷題：找出最大元素的位置

02.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.3 找出陣列中最大(或最小)的元素

03.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.2 刪除陣列中的指定位置的元素

04.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.1 插入元素到陣列中的指定位置

05.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題10：找出小於 n 的質數

06.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題11：從陣列中找出相加等於 k 的兩數

07.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.1 下列程式片段執行的輸出為何？

08.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.2 資料儲存於 A[0] ~ A[ n-1 ]。

09.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.3 下述程式擬找出陣列 A 中的極值

11.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題12：找零錢問題

12.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題13：比例背包問題

13.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題14：最少裝箱浪費問題

14.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題15：最大子陣列(Maximum Subarray)

15.資料結構-第2章陣列 Array 題目-2-D Array 的運算-範例 2.4 矩陣的輸出

 

from math import inf

def packing(packages,boxes):

    min_waste = inf

    supFound = False

    print('len(boxes) = ',len(boxes))

    for s in range(len(boxes)):

        print('s = ',s)

        cur_waste = 0

        p = 0

        b = 0

        print('len(boxes[s]) = ',len(boxes[s]))

        while b < len(boxes[s]):

            print('b = ',b)

            print('packages[p] = ',packages[p])

            print('boxes[s][b] = ',boxes[s][b])

            while packages[p] <= boxes[s][b]:

                cur_waste = cur_waste + (boxes[s][b] - packages[p])

                print('cur_waste = ',cur_waste)

                p = p + 1

                print('p = ',p)

                print('len(packages) = ',len(packages))

                if p >= len(packages):

                    min_waste = min(cur_waste, min_waste)

                    print('min_waste',min_waste,'cur_waste = ',cur_waste,'min_waste = ',min_waste)

                    supFound = True

                    break

            b = b + 1

            print('b = ',b)

            print('p = ',p,'len(packages) = ',len(packages))

            if p >= len(packages):

                break

    print('supFound = ',supFound)

    if supFound:

        print('min_waste = ',min_waste)

        return min_waste

    return -1

packages = [2,3,5]

m = 2

boxes = [[4,8],[2,8]]

print(packing(packages,boxes))