日期: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;
}
沒有留言:
張貼留言