每日一题————2026-7-8 [背包-二]

K11628 - 背包-二

题目描述

有个背包可承受重量T，现有N件物品，每件物品重量为Wi,价值为Vi ,每件物品的数量是无穷的,这个背包可以装载物品的最大价值是多少?

输入格式

第一行，两个整数，分别表示T和N，用空格隔开（T≤1000，N≤100）

接下来N行，每行两个整数，分别表示N件物品的重量Wi和价值Vi（1≤Wi,Vi≤100）

输出格式

一行，表示这个背包可以装载物品的最大价值

输入输出样例

输入样例1：

100 5 77 92 22 22 29 87 50 46 99 90

输出样例1：

261

参考AC代码：

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
LL dp[1010];
int main(){
LL T, N;
scanf ("%lld %lld", &T, &N);
for (LL i = 1, w, v;i <= N;i ++){
scanf ("%lld %lld", &w, &v);
for (LL j = w;j <= T;j ++) dp[j] = max(dp[j], dp[j - w] + v);
}
printf ("%lld", dp[T]);
return 0;
}