首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> 更多程式語言 >> 程式設計疑難解答

HDU 動態規劃:AC boy needs your help (分組背包/多重選擇)

     編輯:程式設計疑難解答

題目模型

N 門課,最多 M 天。第 i 門課花 j 天獲得收益 A[i][j]。每門課**恰好選擇一種**天數(或 0 天),總天數 ≤ M,最大化總收益。
這是**分組背包**(每組必選一項)或**多重選擇背包**問題。

狀態定義

`dp[i][j]`:前 i 門課用 j 天的最大收益。
轉移:`dp[i][j] = max(dp[i-1][j-k] + A[i][k])` for k=0..j(k=0 表示不選這門課)。

優化:一維數組逆序

int dp[101] = {0};
for (int i = 1; i <= N; i++) {
    for (int j = M; j >= 0; j--) {
        for (int k = 1; k <= j; k++) {
            dp[j] = max(dp[j], dp[j-k] + A[i][k]);
        }
    }
}
answer = dp[M];

複雜度

  • 時間 O(N * M^2),N,M ≤ 100 → 10^6 操作,極快。
  • 空間 O(M)。

參考題解

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved