题解 | 【模板】完全背包

#include <bits/stdc++.h>
using namespace std;
using ll =long long;  // 将long long别名化为ll，避免整数累加时的溢出问题
const ll N=1e3+5;    // 定义背包容量的最大范围：题目中m≤1e3，因此设1e3+5确保数组足够

struct it{
    ll w=0;  // 物品的体积
    ll v=0;  // 物品的价值
};

ll f[N];  // 完全背包的dp数组：f[j]表示“背包容量为j时，能装下的物品的最大总价值”

int main() {
    // 加速输入输出：解除cin与cout的同步绑定、关闭stdio缓冲，避免多组数据时输入输出超时
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin>>T;  // T为测试数据的组数
    while(T--){  // 循环处理每组测试数据
        ll n,m;
        cin>>n>>m;  // n：物品数量；m：背包的最大容量
        it a[n+1];  // 存储n个物品的结构体数组
        memset(f,0,sizeof f);  // 每组测试前重置dp数组f为0，避免上一组数据的影响
        for(ll i=1;i<=n;i++){
            // 输入第i个物品的体积w和价值v，存入结构体数组a
            cin>>a[i].w>>a[i].v;
        }
        ll res=0;  // 记录当前测试组中，背包能装下的最大价值
        // 完全背包核心算法：遍历每个物品，更新所有容量的最大价值
        for(ll i=1;i<=n;i++){  // 外层循环：依次处理第i个物品
            // 内层循环：j从物品体积a[i].w开始正序遍历到m（完全背包的关键：正序允许物品被多次选取）
            for(ll j=a[i].w;j<=m;j++){
                // 状态转移：容量j的最大价值 = max(不选当前物品的价值f[j], 选当前物品的价值f[j-a[i].w]+a[i].v)
                if(f[j]<f[j-a[i].w]+a[i].v){
                    f[j] = f[j-a[i].w] + a[i].v;  // 更新容量j的最大价值
                    res = max(res,f[j]);  // 维护当前的全局最大价值
                }
            }
        }
        cout<<res<<endl;  // 输出当前测试组的最大价值
    }
   return 0;
}