2013-01-21 07:00:32Morris
[ZJ][0/1背包] a587. 祖靈好孝順 ˋˇˊ
內容 :
快要農曆春節過年了!!!!!!
小小高中生 "祖靈"歡歡喜喜地準備回家。
他在玩 "Defender II" 時拿到了很多很多的寶物!!!!!
可是寶物分別有各自的重量和價值(換算成金幣)。
孝順的祖靈當然要把寶物帶回老家孝敬父母啊!!!
可是.....他的背包有重量限制!!!!
給出N個物品和物品的重量和價值。
最後給出祖靈他的背包的重量限制。
請告訴祖靈他最多可以帶價值多少金幣的東西回老家!!!!
輸入說明
:
有1000組測試資料。
每筆測試資料開頭給出N,也就是祖靈有多少寶物。
接下來有N行,分別代表每個寶物的重量和價值。
再來給出祖靈他背包背包的重量限制。
範圍:0<N<=100 , 0<=重量, 價值<=2000 , 0<重量限制<=10000
輸出說明
:
輸出祖靈最多可以帶價值多少金幣的東西回家。
答案不會超過int的範圍。
範例輸入
:
4 2 3 1 2 3 4 2 2 5
範例輸出 :
7
提示
:
出處
:
/**********************************************************************************/
/* Problem: a587 "祖靈好孝順 ˋˇˊ" from 祖靈的的大背包 */
/* Language: C (634 Bytes) */
/* Result: AC(260ms, 336KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-20 10:07:42 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
int main() {
int N, M, p[100], w[100], i, j;
while(scanf("%d", &N) == 1) {
for(i = 0; i < N; i++)
scanf("%d %d", &w[i], &p[i]);
scanf("%d", &M);
int dp[M+1];
memset(dp, 0, sizeof(dp));
for(i = 0; i < N; i++) {
for(j = M; j >= w[i]; j--)
if(dp[j] < dp[j-w[i]] + p[i])
dp[j] = dp[j-w[i]] + p[i];
}
int ans = 0;
for(i = 0; i <= M; i++)
if(dp[i] > ans)
ans = dp[i];
printf("%d\n", ans);
}
return 0;
}