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