国庆day5背包总结-->上午

Crash_Man_CHN · 2025-10-08 19:53:40 · 个人记录

背包

类型

1.01背包
2.完全背包
3.多重背包
4.分组背包

01背包

出题形式

给定容量为m的背包有n个物品，第i个物品重量为w[i]价值为d[i],求该背包能放入的物品的最大价值之和

解题方法

四步法：

1.状态：dp[i][j]表示在前i个物品中选取物品，容量为j时，可以得到的最大价值

2.答案：dp[n][m]

3.转移：

if(j<w[i])dp[i][j]=max(dp[i][j],dp[i-1][j]+d[i]);
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+d[i]);

4.初始化： dp[0][j]=0;

实现代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,w[N],d[N],dp[3405][12885];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i]>>d[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+d[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][m];
    return 0;
}

可这个方法稍微数据大点，就会TLE和MLE

优化(滚动数组)

所以我们可以用滚动数组优化：优化空间复杂度，不改变时间复杂度;

也就是可以将dp从2维改成1维，具体实现代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int w[N],d[N],dp[N];
int n,m;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i]>>d[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
        }
    }
    cout<<dp[m];
    return 0;
}

例题

1.P1802 5倍经验日

该题几乎都是板子，重量是打过要至少使用的药数量，代价是win[i]和llose[i]这个经验，但是要注意的就是即使装不下（题目里也就是打不过）也有代价（经验），最后输出要乘5即可

实现代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int lose[N],win[N],w[N],dp[N];
int n,m;
//价值-> 经验 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>lose[i]>>win[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            if(j>=w[i])dp[j]=max(dp[j]+lose[i],dp[j-w[i]]+win[i]);
            else dp[j]=dp[j]+lose[i];
        }
    }
    cout<<5*dp[m];
    return 0;
}

重点题型

例题：CF577B

先读题，读完题后，可以按一下步骤思考

① 每个数可选可不选，且选择顺序不影响求和，考虑01背包

② 每次选一个数，和就会发生变化，而当和模m的余数为0代表整除，所以我们将研究对象转化为余数

③ 四步法