国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

小P尋寶記——粗心的基友

2019-11-09 20:09:22

字體：大中小

來源：轉載

供稿：網友

PRoblem Description

這對好基友他們在經歷無數的艱難險阻后，終于找到了寶藏。無奈的是這一對好基友竟然是一樣的粗心，又忘記了帶一個大一點的包包，可惜啊、、選擇又出現了啊、、已知包的體積是v，每種寶貝只有一個，寶貝的體積是pi，價值是wi。求出這對粗心的基友可以最多帶走價值多少的寶藏。

Input

輸入數據有多組。每組第一行有兩個正整數n(n <= 10000)和v(v <= 10000)分別表示n種寶貝和包的體積。接下來n行，每行有兩個正整數vi， wi。分別表示每種寶藏的體積vi （vi<=1000）,價值wi(wi<=1000)。

Output

這對基友所能帶走的最多的寶藏。

Example Input

5 10 1 52 43 34 25 1Example Output
14Hint
01背包問題， 提交時總是runtime error 好煩。
01 #include<stdio.h>
02 #include<string.h>
03 int f[10004], v[10004], w[10004];
04 int max(int a, int b)
05 {
06     return a > b? a : b;
07 }
08 int main()
09 {
10     int n, V, i, j;
11     while(scanf("%d%d", &n, &V) != EOF)
12     {
13         memset(f, 0, sizeof(f));
14         memset(v, 0, sizeof(v));
15         memset(w, 0, sizeof(w));
16         for(i = 0; i < n; i++)
17             scanf("%d%d", &v[i], &w[i]);
18         for(i = 0; i < n; i++)
19         {
20             for(j = V; j >= v[i]; j--)
21             {
22                 f[j] = max(f[j], f[j - v[i]] + w[i]);
23             }
24         }
25         printf("%d/n", f[V]);
26     }
27     return 0;
28 }