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

問題：有個小偷的背包總容量 W_limit，要打包 n 種物件帶走，每種物件只有 1 個，重 wi、價值pi，如果物件可以切割裝袋，請計算最高的打包價值。

執行範例：輸入為

30
  3
  A  B     C
  5 10   20
50 60 140

其意義如下：

總容量 30

3 種物件分別為 A B C

各物件重量分別為 5 10 20

各物件價值分別為 50 60 140

def backPack(arrs,w_l):

    total_price = 0

    i = 0

    left_weight = w_l

    while i < len(arrs) and left_weight > 0:

        if arrs[i][2] <= left_weight:

            total_price = total_price + arrs[i][3]

            left_weight = left_weight - arrs[i][2]

        else:

            total_price = total_price + arrs[i][0]*left_weight

            left_weight = 0

        i = i + 1

    return total_price

w_limit = int(input())

n = int(input())

names = [i for i in input().split()]

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

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

items =[[] for _ in range(n)]

for i in range(n):

    items[i] = [prices[i]/weights[i],names[i],weights[i],prices[i]]

items.sort(reverse=True)

print(backPack(items,w_limit))

 

資料來源：

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

2.背包問題

 

題目目錄

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 矩陣的輸出