#28058: 解題思路


goodsssdd1@gmail.com (惠惠大主教)

School : No School
ID : 114918
IP address : [140.113.122.26]
Last Login :
2021-11-22 10:15:25
d390. 00562 - Dividing coins -- UVa562 | From: [140.113.122.26] | Post Date : 2021-11-12 11:35

按照提示完整度往下排,看到當前提示先思考一下,真的想不到再繼續往下一點看

 

1.這題可以轉換成01背包問題

 

 

 

 

 

2.假設所有錢幣的面額加起來等於S,題目目標是兩堆錢金額差值最小,等同於找出能組合出價值最接近但不超過[S/2]的金錢堆

 

 

 

 

 

 

3.轉換成01背包問題的話,每個錢幣可以看成價值Xi,重量Xi的物品,而背包能乘載的重量為[S/2],Xi為錢幣的面額

 

 

 

 

 

4.假如第三點的背包問題求出的最大價值為M,則另一堆錢幣的總額即為S-M,兩者的差值即為答案

 
#30914: Re: 解題思路


100200 (Yu Xuan)

School : 高雄市立高雄高級中學
ID : 169890
IP address : [101.8.39.61]
Last Login :
2024-05-08 18:03:53
d390. 00562 - Dividing coins -- UVa562 | From: [119.14.97.194] | Post Date : 2022-06-21 17:04

按照提示完整度往下排,看到當前提示先思考一下,真的想不到再繼續往下一點看

 

1.這題可以轉換成01背包問題

 

 

 

 

 

2.假設所有錢幣的面額加起來等於S,題目目標是兩堆錢金額差值最小,等同於找出能組合出價值最接近但不超過[S/2]的金錢堆

 

 

 

 

 

 

3.轉換成01背包問題的話,每個錢幣可以看成價值Xi,重量Xi的物品,而背包能乘載的重量為[S/2],Xi為錢幣的面額

 

 

 

 

 

4.假如第三點的背包問題求出的最大價值為M,則另一堆錢幣的總額即為S-M,兩者的差值即為答案

照你的說法 範例測資是對了沒錯 但後面就不好說了

 
ZeroJudge Forum