派對時間表 - 古典揹包

輸入是一個可用的預算，派對數量，每個派對的門票價格和聚會上的樂趣。任務是通過可用的預算和使用的預算輸出儘可能多的樂趣。如果您可以選擇同樣樂趣的兩方，請選擇便宜的一方。（這是一個SPOJ problem。）派對時間表 - 古典揹包

我創建了兩個數組：

m[i][j]從各方得到最大的樂趣多達我預算Ĵ
p[i][j]最低價格PY來獲得最大的。從各方多達我與預算Ĵ樂趣

然後，對每個I高達#parties和對每個j達到預算我計算的m[i][j]和p[i][j]值是這樣的：

for(T i = 1; i <= parties; i++) { 
    for(T j = 0; j <= budget; j++) { 
     //We get more fun by attending party i 
     if(price[i] <= j && m[i-1][j-price[i]] + fun[i] > m[i-1][j]) { 
      m[i][j] = m[i-1][j-price[i]] + fun[i]; 
      p[i][j] = p[i-1][j-price[i]] + price[i]; 
     //We get same fun by attending i, but more cheaply 
     } else if(price[i] <= j && m[i-1][j-price[i]] + fun[i] == m[i-1][j] && p[i-1][j-price[i]] + price[i] < p[i-1][j]) { 
      m[i][j] = m[i-1][j-price[i]] + fun[i]; 
      p[i][j] = p[i-1][j-price[i]] + price[i]; 
     //We can't visit the party 
     } else { 
      m[i][j] = m[i-1][j]; 
      p[i][j] = p[i-1][j]; 
     } 
    } 
}

對於我發現的任何測試用例（如果需要，我可能會共享一些測試用例），該算法輸出的結果與網上裁判批准的算法相同。但是，這個沒有批准。

該算法有什麼問題？

Here是完整的程序。

來源

2014-08-31 mirgee

我檢查你的完整代碼，而無需通過你的邏輯走，但也有一些必須待錯點：

您decalred內部功能的price數組作爲price[parties]，只允許price[0..parties - 1]，但你使用最多price[parties]，與fun[]相同;
您的while的條件是while(scanf("%u %u",&budget,&parties), budget != 0 && parties != 0)，但是即使在有效輸入中，budget也可以是0，因此您的程序可能會比預期更早終止;
你宣佈你的m[][]和p[][]內函數，但沒有初始化它，所以它會被填滿垃圾值;
您使用printf("%u %u")打印答案，但問題需要每個輸出的新行，因此這裏應該是printf("%u %u\n")。

後，我改變了你的程序這4個「錯誤」，它就會被接受:)所以你的算法邏輯被批准，但一些「不相干」的東西阻止你得到接受。 不要小看這些「細節」，它們會算數！

來源

2014-09-01 01:43:06 nevets

派對時間表 - 古典揹包

回答

相關問題