多項式子集和求和的僞多項式或快速求解

我正在尋找多項/多目標subset-sum problem的快速解決方案。由於附加約束（使得小魚更易於計算IMO），我們可以假設所有包含在總和中的值都是正數，並且都被限制在一個已知的極限值上。多項式子集和求和的僞多項式或快速求解

我知道有一個O（NK）假多項式解的單目標子集求和問題，我已經實現了一個基於維基百科和this堆棧交換答案的解決方案。

以其他方式解釋這個問題，我有兩組正數，這些限值是已知的。對於第一個集合中的每個值A，第二個集合中的值的總和等於A.第一集合中的所有值都具有與第二集合中相關聯的值相對應而非衝突的組合，爲有一種已知的快速方法來計算第二組中的哪些元素與每個第一設定值相關聯？

2012-07-13 viniciuscb

你是什麼意思的「不衝突」？你的意思是第二組中的每個值只用於創建A中的一個值？或者，你是否也許意味着A中每個解的值都是唯一的（即只有第二組中的一個子集會產生那個值）或者其他的東西？ – 2012-07-13 20:29:44

@JerryCoffin，第二組中的每個值僅用於創建A中的一個值。 – viniciuscb 2012-07-13 20:35:39

在這樣的問題中，第二組中可以有幾個組合，可以總計爲第一組中的值。問題是，我們必須爲第一組中的每個值找到一個組合，並且所有找到的組合在第二組中使用排他值 - 這就是我說他們不衝突時的意思。 – viniciuscb 2012-07-13 20:41:21

我認爲你的問題是多重約束問題的變化，我在我的碩士論文中學習過。

在這個項目中，我設計了一個算法，在DP表中搜索找到解決方案。這不是僞多項式，但我認爲它在一般情況下足夠快。

我還實現了一個Python工具來解決這些問題。也許你想試試！

這個工具叫做msat它在github上維護。您可以參考msat。

或者乾脆用pip安裝它（這是一個Python3工具）：

$ pip install msat

也有介紹的幻燈片：slides。

如果您想知道詳細信息，請參考thesis。

2016-04-21 19:37:08 dokelung

回答