使用DP最大化利潤？

Question

我有一個算法問題。我試着解決，但無法得到解決方案。我知道它可以使用dp來解決，但是沒有獲得足夠的利基。使用memoization算法的遞歸dp對我來說是理想的。即使是一個小提示或鏈接也可以。這個問題的說法是：

「一位店主有‘N’重的蘋果一個_我在任何一天，他賣出正是蘋果的一個，但由於細菌，蘋果失去它們的權重，因此店主賺取。一個利潤_我％d的（即_我 MOD d）時，他賣出重量的蘋果_我一天「d」。 什麼是最大的利潤店主可以使」

輸入： 第一行是'n'，第二行包含n個蘋果的權重。

實施例：

輸入：

輸出：

說明：店主出售蘋果4上第一天第二天的蘋果3。因此，利潤= 4％1 + 3％2 = 1

Answer 1

根據我可以解決使用最大權重匹配在二分圖。

店主有n蘋果，他必須分配每個蘋果從1 to n一天。他也知道相關的利潤。

因此一個nxn可以形成完整的二分圖，並且可以使用匈牙利算法獲得最大的權重匹配。