是的，這是家庭作業。我已經嘗試了幾個小時，但仍然遇到相同的想法，所以我只是要求某人給我一些正確方向的提示，其余的取決于我，我不是在尋找完整的解決方案。也就是說問題如下。
假設你有n 個朋友想要給你一筆錢來幫助你購買一部新的智能手機。他們每個人都聲稱一個值 m_r 代表朋友r愿意給你的最大金額。您與朋友的友誼程度可以分為以下幾類：您的親密朋友與您的距離為 1。然后有距離你 2 的朋友，依此類推，直到距離k的朋友與你的友誼不那么牢固。你必須告訴你的每個朋友一個數量g_r代表您希望從他/她那里得到什么。為了與友誼層次結構保持一致，您需要滿足以下約束條件：假設友誼是通過函式f(r)來衡量的，您最親密的朋友之一r_1的距離為f(r_1) = 1并且對于另一個在距離 3 處，r_2，它是f(r_2) = 3，那么你不能問r_3一個數量g_3 > g_1。一般來說，對于每對朋友r_i和r_j，如果f(r_i) < f(r_j)那么也必須是g_i >= g_j。為每一個朋友r你可以問一個數量g_r > m_r但在這種情況下，那個朋友會給你 0。目標是計算每個朋友要問的數量，以最大化收到的總金額。
我的問題出現在最后一個粗體句子上。如果只是你不能問某人比他/她聲稱的數額大的情況，那么存在一個非常簡單的貪婪方法來解決這個問題，但由于它可能發生在最后一句話，在某些情況下可以方便地問你親戚朋友的金額大于他們聲稱的金額，并從他們那里得到零，以便從非常慷慨的油炸食品中獲得非常高的禮物（要獲得這樣的金額，您必須向他索要，而對于等級制度，您必須至少詢問在層次結構中與他之上的所有朋友相同，這導致從他們那里得到零）。
我猜的方式是動態規劃，那是因為問題似乎有：
- 重疊子結構：不同的友誼距離，稱這些“層”相互影響，實際上一層的最小要求量設定了更深層的upper_bound。
- 最佳子結構：如果我找到 j 層問題的最佳總和，這可用于構建具有 j 1 層的解決方案，實際上我應該選擇是否值得為層 j 1 或如果是這樣的話，為了從第 j 1 層的朋友那里獲得收入，需要“犧牲”來自 1...j 層的一些朋友的幫助。
謝謝
uj5u.com熱心網友回復：
暗示。由外而內。
在最外層，建立一個字典，記錄你能問的最多的問題，以及你能得到多少。（這是一本有限詞典，因為要求與某人愿意提供的金額不同的金額是沒有意義的。）
當你走進去，如果你問G(k 1)一個人在的k 1層，并在你的最大要求k日層G(k)，你賺多少是你從最大的要求外層賺多少錢已經G(k)加任何人在任何該k次層是誰只肯給不到G(k 1)，再加上所有他們愿意給那些誰愿意從任何地方給G(k 1)到G(k)（注意，G(k)必須是大于或等于G(k 1)因您的規則），以及G(k)從誰可以已經愿意得到更多。
跟蹤您可以賺多少錢，以及在賺錢的道路上進行了哪些跳躍。
當您到達內圈時，您可以找到最大值，然后走出路徑以獲得導致該最大值的解決方案。
uj5u.com熱心網友回復：
以下是應該有效的前向 DP 方法的概要：
列出
V[]所有提供的值m_r，從最低到最高排序。列出你所有的朋友 (
D[])，從最遠到最接近。如果出現平局，請將較低的放在m_r較高的之前m_r。我們將使用D[x].m來代表您的朋友在 中提供的價值D[x]。制作一個nxn陣列(
A[])，其中行A[x,*]對應于已排序的朋友串列D[x]，列A[*,y]對應于已排序的值V[y]。使用以下方法填寫第一行 (
x=0, y=(0 to n-1))：A[0,y] = {if V[y] <= D[0].m Then V[y] Else 0}使用以下公式填寫下一行：
A[x,y] = {if V[y] <= D[x].m Then V[y] Else 0} MAX(A[x-1,j] for j=0 to y)
您可以獲得的最大值是最后一行中的最大值。可以j通過MAX(..)步驟 5 中的函式為每一行選擇哪個值來確定要詢問每個朋友的值。
這將在O(n^3). 有一種聰明的方法可以預先計算并保存MAX(A[x-1,j] for j=0 to y)每個值，A[x-1,y]從而將其減少到O(n^2).
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/363820.html