A30661.完全背包 最好的题解

现在acgo还有这种模板题，挺奇怪的。
我也是而话不多说，直接开整！

完全背包模板题，先看数据: m<201,n<31
可以直接用二维数组dp。

状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-wt[i]] + val[i])

#include<bits/stdc++.h>
using namespace std;

const int maxn=101010;
int wt[maxn], val[maxn];
int dp[maxn][maxn];  // dp[i][j]：前i个物品，容量j的最大价值
int v, n;

int main(){
    cin >> v >> n;
    for(int i=1; i<=n; i++)
        cin >> wt[i] >> val[i];

    for(int i=1; i<=n; i++){
        for(int j=0; j<=v; j++){
            // 不选第i件，继承上一层
            dp[i][j] = dp[i-1][j];
            // 能装下就尝试选当前物品（本行状态，从小到大实现无限取）
            if(j >= wt[i])
                dp[i][j] = max(dp[i][j], dp[i][j - wt[i]] + val[i]);
        }
    }
    cout << dp[n][v];
    return 0;
}

如果还有不知道啥是背包的新手们，赶紧学习动态规划吧！

这边另外推荐几个背包的题目（不好弄链接，请见谅）：

A30745.【动态规划】【背包】01背包
A607.多重背包
A30748.【动态规划】【背包】装箱问题

回归正题，这道题虽然数据很小，但是还需要让大家熟悉更优的一维写法

状态转移方程：dp[j]=max(dp[j], dp[j-wt[i]]+val[i])
代码如下：

#include<bits/stdc++.h>
using namespace std;

// maxn数组上限，适配物品数量、背包容量最大101010
const int maxn=101010;
int wt[maxn];   // wt[i]：第i件物品的重量
int val[maxn];  // val[i]：第i件物品的价值
int dp[maxn];   // 一维dp数组，dp[j]表示背包容量为j时能装的最大价值
int v, n;       // v：背包总容量；n：物品总件数

int main(){
    // 读入背包容量v、物品数量n
    cin >> v >> n;
    // 依次读入每个物品的重量、价值，下标从1开始方便循环
    for(int i=1; i<=n; i++)
        cin >> wt[i] >> val[i];

    // 遍历每一件物品
    for(int i=1; i<=n; i++){
        // 完全背包核心：容量从小到大遍历
        // j从wt[i]开始，小于物品重量直接不用处理
        for(int j=wt[i]; j<=v; j++){
            // 两种选择取最大值：
            // 1. dp[j]：不拿当前第i件物品，保留原来的最优解
            // 2. dp[j-wt[i]]+val[i]：拿当前物品，剩余容量j-wt[i]继续放（可重复拿）
            dp[j] = max(dp[j], dp[j-wt[i]] + val[i]);
        }
    }
    // 输出容量为v时背包能装的最大价值
    cout << dp[v];
    return 0;
}

随时可以联系我
求关注~