ZeroJudge 解題筆記：d637. 路過的鴨duck

作者：王一哲
日期：2025年9月9日


ZeroJudge 題目連結：d637. 路過的鴨duck

解題想法

這題考 0/1 背包問題，我習慣的寫法是先建立一個一維陣列 dp，分別對應食量為 0 ~ 上限 imax 對應的最大飽足感總和。依序讀取每個食物的體積 a 及飽足感 b，從 dp[imax] 往回更新總和至 dp[a] 為止，取 dp[i] 與 dp[i-a] + b 較大者，最後答案在 dp[imax] 。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 3.3 MB，通過測試。

n = int(input())  # n 顆飼料
imax = 100  # 食量上限
dp = [0]*(imax + 1)  # 吃 0 ~ 100 分別對應的最大飽足感
for _ in range(n):  # 依序讀取 n 行資料
    a, b = map(int, input().split())  # 飼料的體積 a、飽足感 b
    for i in range(imax, a-1, -1):  # 倒序檢查飽足感 imax ~ a
        dp[i] = max(dp[i], dp[i-a] + b)  # dp[i-a] + b 可能更大
print(dp[imax])  # 印出最大值

C++ 程式碼

使用時間約為 4 ms，記憶體約為 80 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // n 顆飼料
    const int imax = 100;  // 食量上限
    int dp[imax + 1] = {0};  // 吃 0 ~ 100 分別對應的最大飽足感
    for(int j=0; j<n; j++) {  // 依序讀取 n 行資料
        int a, b; scanf("%d %d", &a, &b);  // 飼料的體積 a、飽足感 b
        for(int i=imax; i>=a; i--) {  // 倒序檢查飽足感 imax ~ a
            int new_val = dp[i-a] + b;  // dp[i-a] + b 可能更大
            if ((new_val) > dp[i]) dp[i] = new_val;
        }
    }
    printf("%d\n", dp[imax]);  // 印出最大值
    return 0;
}