d637: 路過的鴨duck

內容

有一天
有一隻路過的鴨 duck

牠…太餓結果就死了囧…

當他到天國的時候，
遇到了先前駕崩的鴨子王(duck king)，
牠變成了管理鴨子靈魂的神(duck king god，簡稱 duckingod)

duckingod 生前是一隻非常聰明的神鴨，
所以 duckingod 給這隻路過的鴨一個復活的機會。
給牠一袋鴨飼料，裡面的每顆飼料有不同的體積和飽足感
只要路過的鴨能夠在有限的食量內吃得最飽，
那牠就能復活了！

快寫個程式幫幫路過的鴨吧！呱呱呱！

輸入

每個測資點僅一組測資，不必 EOF 讀檔。
第一行有正整數 n(1<n<=10000)表示有 n 顆鴨飼料
接下來的 n 行，每行有 ab 兩個正整數，
a 代表這顆鴨飼料的體積，b 代表飽足感(1<=a<=100 , 1<=b<=5000)
並且鴨子最多可以吃滿 100 體積的飼料。

6
10 8
25 25
65 75
25 29
25 17
15 20

輸出

請輸出這袋鴨飼料能帶給路過的鴨的最大飽足感！

112

解題思路

經典的背包問題，飼料不能重複使用所以每種飼料從最大(100)飽足感 DP 到最小(飼料)飽足感。

完整程式碼

AC (4ms, 116KB)

#include <stdio.h>

int DP[101];

int main()
{
    int n, a, b;
    scanf(" %d", &n);
    while (n--)
    {
        scanf(" %d %d", &a, &b);
        for (int i = 100; i >= a; i--)
        {
            if (DP[i] < DP[i - a] + b)
                DP[i] = DP[i - a] + b;
        }
    }
    printf("%d", DP[100]);
    return 0;
}