請問提出問題，需要註冊嗎

我們提出問題都是需要註冊的。

請問註冊資料安全嗎

我們平台資料都是有加密過，使用者不須擔心。

提出的問題可以刪除嗎

可以的，提出的問題會出現在會員中心(我的裡面)，可以做刪除的動作。

如果有人回覆我的廣告，我看的到嗎

可以的，登入會員後，在訊息中心可查詢。

計算數學ProblemSolving-ZJ-b952背包問題(?) - 答案王【免費查問題答案平台】台灣知識+ |提供跟知識+一樣的知識問答服務

Q: 請問提出問題，需要註冊嗎

我們提出問題都是需要註冊的。

Q: 如果有人回覆我的廣告，我看的到嗎

可以的，登入會員後，在訊息中心可查詢。

刊登資訊

刊登者：匿名
時間：2021-06-05 13:40:13

尚未解答計算數學 Problem Solving- ZJ-b952 背包問題(?)

計算數學 Problem Solving- ZJ-b952 背包問題(?)

如題，題目是一系列的從簡單的DFS(b942: 轟轟島)

再到經典的01背包問題轉換為分堆問題(b951: 轟轟轟轟島)透過演算法的動態規劃解題，

最後是大魔王的這題(b952: 轟轟轟轟轟轟島)。

觀察輸入的測資可以發現輸入的數字雖然只有1e4個，但數字總和可高達2147483647

這樣該怎麼把分堆問題的概念套用到這題呢？還是說有不同思維的解決方式(?)

完全沒有頭緒或是關鍵字可以搜索(可以區隔開背包問題)...

=== 以下是作弊方法並不存在最佳解 ===

背包問題本身就是 NP-hard Problem，不存在多項式時間內的解法。

具體的介紹就請大家到wiki上看看：https://pse.is/GPDME

根據 boqCAE 大大提出的判斷方式，先判斷 N<=30，否則就將一半的總和視為最佳解。

但這個說法顯然是不正確的，比如有9999個31時是會出現問題的...，所以才會是作弊法

只討論當 N<=30 時是否可以有效解決。

一般採用 DFS 搭配有效的剪枝但會卡在第一筆測資TLE吃到飽。

感謝 vincent97198 的測試：https://ideone.com/GnKv1U

TLE的主要原因是第一筆測資的第一個case(再作弊一次...直接輸出答案)，

剪枝(內容我寫在註解)加上GCC的優化代碼，具體優化的原理...

我看了一遍知乎上的討論還是半懂不懂(https://www.zhihu.com/question/27090458)

我自己採用雙向BFS的概念，將30組數字分成兩組各自產生 2^15 (32768)個數字。

做二分搜尋配對找到最接近總和一半的組合。

雙向 BFS 作法：https://ideone.com/GnKv1U

TLE主因是第二筆測資，我測試後的上限是 N<=42 再多也是吃TLE。

--

贊助廠商

首頁

刊登資訊

尚未解答計算數學 Problem Solving- ZJ-b952 背包問題(?)

計算數學 Problem Solving- ZJ-b952 背包問題(?)

0個答案計算數學 Problem Solving- ZJ-b952 背包問題(?)

其他問題

友站連結

贊助廠商

首頁

刊登資訊

尚未解答計算數學 Problem Solving- ZJ-b952 背包問題(?)

計算數學 Problem Solving- ZJ-b952 背包問題(?)

0個答案 計算數學 Problem Solving- ZJ-b952 背包問題(?)

其他問題

友站連結

0個答案計算數學 Problem Solving- ZJ-b952 背包問題(?)