m個(gè)任務(wù)，第i個(gè)任務(wù)需要Xi的時(shí)間去完成，難度為Yi。有m臺(tái)機(jī)器，第i臺(tái)機(jī)器最長(zhǎng)工作時(shí)間為Zi，機(jī)器等級(jí)為Wi。對(duì)于一個(gè)任務(wù)只能交由一臺(tái)機(jī)器完成，任務(wù)被完成的條件為：任務(wù)所需時(shí)間Xi小于機(jī)器最長(zhǎng)工作時(shí)間Zi，任務(wù)難度Yi小于等于機(jī)器等級(jí)Wi。任務(wù)被第i臺(tái)機(jī)器完成的收益為200*Xi+3*Yi。一臺(tái)機(jī)器只能分配一個(gè)任務(wù)。想完成盡可能多的任務(wù)，若有多種方案，求收益最大的那個(gè)？輸入：共m+n+1行第一行：n m接下來n行：Zi Wi接下來m行：Xi Yi輸出：任務(wù)完成數(shù) 收益示例：輸入1 2100 3100 2100 1輸出1 20006
1 回答
拉風(fēng)的咖菲貓
TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊
我感覺，把任務(wù)排個(gè)序，把箱子排個(gè)序，從大到小，然后按照順序把任務(wù)依次放到箱子里。因?yàn)橐粋€(gè)機(jī)器只能裝一個(gè)任務(wù)，所以就不是背包問題了。一個(gè)機(jī)器只能完成一個(gè)任務(wù)，當(dāng)然是選擇收益最高的那個(gè)任務(wù)去完成。把任務(wù)收益從大到小排序，依次完成。
添加回答
舉報(bào)
0/150
提交
取消