c264. 神奇的載物任務
標籤 :
通過比率 : 57人/67人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-09-16 14:36

內容

  一天,小紫被賦予了一個運送貨物的任務,雇主給了她一輛不管是造型或是功能都很奇異的大貨車。

  這輛貨車會先把車後面的一條長條狀的載物臺放下來,每個等間隔距離的位置都裝有一個載物箱,為了防止箱子亂動,每個箱子都被定死了位置。

  雇主告訴小紫,由於他所剩時間不多,希望她到了指定地點後把盡量讓載回來的物品價值最大,這樣生意才至少能夠做的不會太慘,另外就是每個物品都有標示重量和價值,所以不用擔心計算上的問題。

  小紫很順利地將貨車開到了指定地點,面對這些排列整齊的貨物,小紫很輕鬆地就想到了著名的資訊問題──背包問題。 

  「這太簡單了!波路特石教過我!」

  小紫很開心地就寫完了背包問題的程式,實際拿去操作之後才發現事情大條了!將載物臺捲上去的馬達居然無法運作,還發出了恐怖的聲音。

  認為自己計算沒錯的小紫滿腦子疑惑,思索了一陣子才發現問題的關鍵點──力矩!

  重物如果放在離馬達越遠的地方,所造成的力矩就會越大,進而使轉動的困難度大大增加,經過精密的計算後,小紫好不容易才計算出了最大承受上限的力矩,可是卻不知道接下來如何進行下去。

  現在告訴你力矩承受上限為τ(重量×長度),每個箱子間隔都是一長度單位,載物臺的長度最多只能放下L個物品,和每個物品的重量和價值,你能夠告訴小紫她能載回去的最大價值嗎?

輸入說明

輸入首行會有三個數字以空格隔開

分別代表物品數量n、力矩承受上限τ、載物臺長度L

接下來n行各有兩個數字wi、vi以空格隔開,代表第i個物品的重量及價值。

1≤L≤n≤200、1≤τ≤1000、1≤wi、vi≤100

輸出說明

輸出在力矩承受上限內載物可得到的最大價值。

範例輸入 #1
5 120 5
20 30
80 60
30 40
30 25
10 20
範例輸出 #1
90
測資資訊:
記憶體限制: 512 MB
提示 :

Hint

以以下順序擺設物品:

 20   30   10

(30) (40) (20)

所造成的力矩為20×1+30×2+10×3 = 110

得到的價值為 30+40+20=90

也同時是最大價值的選法

 

第1~2測資點滿足n≤20

第3測資點滿足對於所有的1≤i,j≤n都有vi=vj

第4~6測資點滿足n=L

第7~10測資點無特別限制

標籤:
出處:
[管理者:
Unknown User
]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」