HDU 4508チュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウチュウ

キラキラシリーズ——ダイエット記I
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2458    Accepted Submission(s): 1254
Problem Description
食べ物にとって、正月に一番幸せなことは食べることです.一つもありません.
でも女子にとってカロリー(カロリー)は天敵ですよね!
「山のように太って、糸を引くように太っている」という理屈に詳しいので、レシピを作ってあげて、楽しく食べられると同時に、天敵をあまり作らないことを望んでいます.
もちろん、レシピを作るのに便利にするために、
 
Input
複数のテスト・インスタンスが含まれていることを入力します.
各グループのデータは整数nで始まり、毎日の食品リストにn種類の食品があることを示す.
次のn行は、行ごとに2つの整数aとbで、aはこの食べ物が
最後に整数mで、一日中吸収するカロリーがmを超えてはいけないことを示しています.
　　
[Technical Specification]
　　1. 1 <= n <= 100
　　2. 0 <= a,b <= 100000
　　3. 1 <= m <= 100000
 
Output
各リストには、カロリー吸収量を満たすと同時に、最大の幸福値が得られる整数が出力されます.
 
Sample Input

   
   
   
   

    
    
    
    3
3 3
7 7
9 9
10
5
1 1
5 3
10 3
6 8
7 5
6
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    10
20
   
   
   
   

完全リュックサック入門問題.

#include <stdio.h>
#include <string.h>

int dp[100002], w[102], v[102];

int main()
{
    int n, i, j, totalWeight;
    while(scanf("%d", &n) == 1){
        for(i = 1; i <= n; ++i)
            scanf("%d%d", &v[i], &w[i]);            
        scanf("%d", &totalWeight);
        memset(dp, 0, sizeof(dp));
        for(i = 1; i <= n; ++i){
            for(j = w[i]; j <= totalWeight; ++j){
                if(dp[j] < dp[j - w[i]] + v[i])
                    dp[j] = dp[j - w[i]] + v[i];
            }
        }
        printf("%d
", dp[totalWeight]);
    }
    return 0;
}