特殊背包允許部分選取物品而不必整個選取或放棄

白話說這種情況就是物品的數量和重量都可以是分數～

解決這種問題的一種方法是使用貪心算法。貪心算法是一種尋找局部最優解的策略，可選擇當前情況下最好的選擇，而不考慮全局最優解。

在分數背包問題中，我們計算每個物品的價值重量比（value/weight），然後按照這個比率將物品排序，從價值重量比最高的物品開始選取，直到背包被裝滿或所有物品都被選取。

這種方法的優點是簡單且效率高，但它並不保證一定能找到全局最優解，僅僅關注當前的局部最優解。

def fractional_knapsack(C, w, v):
    # 計算物品的價值重量比
    value_per_weight = [(v[i] / w[i], w[i], v[i]) for i in range(len(w))]
    
    # 將物品按價值重量比降序排序
    value_per_weight.sort(reverse=True)
    
    total_value = 0
    selected_items = []
    
    for ratio, weight, value in value_per_weight:
        if C >= weight:
            total_value += value
            selected_items.append((weight, value, 1))
            C -= weight
        else:
            fraction = C / weight
            total_value += fraction * value
            selected_items.append((weight, value, fraction))
            break
    
    return total_value, selected_items

# 測試
C = 50
w = [10, 20, 30]
v = [60, 100, 120]

result, items = fractional_knapsack(C, w, v)
print("最大價值為:", result)
print("選擇的物品:")
for item in items:
    print(f"重量: {item[0]}, 價值: {item[1]}, 比例: {item[2]}")

最大價值為: 240.0
選擇的物品:
重量: 30, 價值: 120, 比例: 1
重量: 20, 價值: 100, 比例: 1
重量: 10, 價值: 60, 比例: 1

這表示在背包容量為 50 時，選擇一些物品放入背包可以獲得的最大價值為 240。選擇的物品及其比例也被列出。