首页 > 代码库 > 01背包
01背包
输入
每一个測试点(输入文件)有且仅有一组測试数据。
每组測试数据的第一行为两个正整数N和M,表示奖品的个数,以及小Ho手中的奖券数。
接下来的n行描写叙述每一行描写叙述一个奖品。当中第i行为两个整数need(i)和value(i),意义如前文所述。
測试数据保证
对于100%的数据,N的值不超过500,M的值不超过10^5
对于100%的数据,need(i)不超过2*10^5, value(i)不超过10^3
输出
对于每组測试数据,输出一个整数Ans,表示小Ho能够获得的总喜好值。
5 1000 144 990 487 436 210 673 567 58 1056 897
2099
#include <stdio.h> #define maxn 100005 int dp[maxn]; int max(int a, int b) { return a > b ?a : b; } int main() { int N, M, i, w, v, j; scanf("%d%d", &N, &M); for(i = 0; i < N; ++i) { scanf("%d%d", &w, &v); for(j = M; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v); } printf("%d\n", dp[M]); return 0; }
01背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。