d637

輸入說明 ：

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

輸出說明 ：

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

0,1背包問題,可以看這篇

假如背包可以放重量為w價值為v的東西

那就去比較放這個東西

(背包重量要減去w,因為你要放這個東西,要把原先w多的東西拿走,價值加上v的加值)

不放這個東西,那就是原本的背包

看誰的價值,比較高,再決定要不要放

#include<stdio.h>

int max(int a,int b)
{
    return (a>=b)?a:b;
}

int main()
{
    int n;
    scanf("%d",&n);

    int lim;
    int w,v; //重量&價值
    int a[101]={0}; 

    while(n--)
    {
        scanf("%d%d",&w,&v);

        lim=100;

        while(lim-w>=0)
        {
            a[lim] = max(a[lim-w]+v,a[lim]);    
            lim--;
        }    

    } 
    printf("%d\n",a[100]);
}