Python中的揹包（什麼？）

我對標題感到抱歉;坦率地說，我甚至不知道我的問題是否與揹包問題有關。正在讀一些關於遺傳算法的東西，並發現這個「揹包問題」。Python中的揹包（什麼？）

我需要有人踢我在正確的方向：

我開發了一個工廠一個python Web應用程序。所以在一家工廠裏，他們有一種叫做訂單的東西。訂單包含一個或多個產品。有一種不匹配的概念，它實際上是一個負數，用來表示特定產品在訂單中出現的數量（以數量表示）。

想象一下矩陣的列是產品，行是訂單。假設所有訂單（行）都包含所有產品（列）。再次，有8個訂單訂單1到訂單8和5個產品，產品1到產品5.

假設，現在我有一個產品1的6不匹配。我需要在所有8個訂單，隨機。所以顯然2個訂單不會有不匹配的數量。然後我對產品2有9的不匹配。我儘可能均勻地分配8個訂單的不匹配數量，隨機。這對每個產品都是如此。現在來了踢球者，雖然我正在將所有Orders中的不匹配項分開，但我需要確保每個訂單（對該行的意義）的總失配保持在最小值。這意味着整個訂單的總不匹配需要儘可能低的數量。

|-----|-----|-----|-----|-----| 
    | P1 | P2 | P3 | P4 | P5 | 
    ------------------------------- 
O1 | 2 | 1 | 1 | 0 | 2 | 6 
    ------------------------------- 
O2 | 1 | 2 | 1 | 1 | 1 | 6 
    ------------------------------- 
O3 | 2 | 2 | 1 | 0 | 1 | 6 
    ------------------------------- 
O4 | 1 | 2 | 0 | 1 | 1 | 5 
    ------------------------------- 
     6  7  3  2  5

你明白嗎？我需要用Python編寫這個代碼，我不知道從哪裏開始。

來源

2012-07-17 Mark

我不明白這一點。如果你有一個零矩陣，並且你給每列添加了一個給定數量的矩陣，那麼矩陣內的總數就是所有列的總和。你不能保持最小數量。（或寫入一些示例代碼與輸入和可能的輸出） – eumiro 2012-07-17 13:38:39

問題是，我不知道從哪裏開始寫任何代碼。那麼，每列可能有不同的數字，9,5,13。然而，當以隨機方式儘可能均等地劃分行數時，我還需要考慮該行的總和（不是列）保持在最低限度。如果一行的總和是13，而其餘的行是3或者什麼的，那意味着行間不匹配的初始劃分不會被同等分割。 – Mark 2012-07-17 13:50:38

使用等寬字體可將矩陣寫爲僞碼。只需將這些行縮進四個空格，它就像代碼一樣。看看其他問題/答案。 – eumiro 2012-07-17 13:53:22

所以OP的問題有兩個要求：隨機和均勻。雖然這有點矛盾，所以我猜「真正的隨機」是不可能的。

這裏是我的嘗試

使用OP的例子，我們有4個訂單，5種產品。從第一個產品開始，我們隨機分配數字，因此每個產品至少有floor（6/4）= 1個不匹配。然後我們隨機將剩下的2個不匹配項放入2個產品中。

|-----| 
    | P1 | 
    ------- 
O1 | 2 | 2 
    ------- 
O2 | 1 | 1 
    ------- 
O3 | 2 | 2 
    ------- 
O4 | 1 | 1 
    ------- 
     6

接下來，我們照顧第二個產品。同樣，我們先隨機分配數字，這樣每個產品至少會有floor（7/4）= 1的不匹配。現在對於剩下的3個不匹配項，儘可能使其爲，甚至，我們首先將它們分配給O2和O4，因爲上次他們的失配比其他的少1個。對於剩餘的1個不匹配，我們再將它隨機分配給一個產品。

|-----|-----| 
    | P1 | P2 | 
    ------------- 
O1 | 2 | 1 | 3 
    ------------- 
O2 | 1 | 2 | 3 
    ------------- 
O3 | 2 | 2 | 4 
    ------------- 
O4 | 1 | 2 | 3 
    ------------- 
     6  7

對所有產品重複此過程。

使用這種方式，你能保證它作爲甚至越好（最大差值爲1），你也得到一定程度的隨機

來源

2012-07-17 20:26:30 xvatar

哇，這是當場。我很驚訝，你甚至明白我想說什麼。現在好吧，當某些訂單中沒有某些產品時會發生什麼情況。例如，如果O3不包含P2？我會盡力根據自己的情況來看看其餘的內容，但非常感謝。你知道這種問題叫什麼，以便我可以更多地瞭解這個？ – Mark 2012-07-18 05:30:10

@Mark很高興幫助:)但是恐怕我不知道是否有這種問題的名稱。祝你好運！ – xvatar 2012-07-18 05:43:09

除了要最小化的目標函數（最大行數）不是線性外，幾乎有一個整數線性規劃問題。請看scipy來解決優化問題。

此線程https://scicomp.stackexchange.com/questions/83/is-there-a-high-quality-nonlinear-programming-solver-for-python也可能有所幫助。

來源

2012-07-17 14:46:51 chepner

假設你做這種方式：

你有一個序列的項目投入的訂單，其中包括第一款產品的項目的順序，其次是第二個產品的項目等

您將第一件物品放入第一物品中，將第二物品放入第二層物品等中，再次圍繞第一層物品進行環繞，直到您沒有物品。

會這樣嗎？

來源

2012-07-17 20:09:35 MRAB

Python中的揹包（什麼？）

回答

相關問題