題意

現(xiàn)有兩方， 給出n個人，每方分別給n個人兩個分?jǐn)?shù)分別為a[i]，b[i]，現(xiàn)要選出m個人，使得m個人兩方的和的差的絕對值最小，如果多組解，輸出雙方和最大的解（?1<=n<=200, 1<=m<=20， 0 <= a[i]，b[i]<= 20）

分析

貪心顯然不可解

錯的思路：dp[i]表示n個人選出i個人的的最佳方案（即絕對值最小），但顯然轉(zhuǎn)移出現(xiàn)問題，dp[i+1]可能不是由dp[i]轉(zhuǎn)移過來的（假如：dp[i] 為1， 但也存在-5， 這時若有有個啊a[i]-b[i]==5，顯然-5轉(zhuǎn)移過里最佳）

正解

定義：dp[i][k]：n個人中選了i個人絕對值為k的最佳方案（和最大）

轉(zhuǎn)移：顯然dp[i][k]（-20*m<=k<=20*k）是由dp[i-1][k+x]轉(zhuǎn)移過來，枚舉一下轉(zhuǎn)移就好，不存在的狀態(tài)用-1表示即可，注意枚舉順序

邊界：dp[0][0]=0，

轉(zhuǎn)載于:https://www.cnblogs.com/Superwalker/p/7912190.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ1015的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。