首页 > 代码库 > 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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。