背包总结

Azazеl · 2019-12-14 14:14:37 · 个人记录

小蒟蒻其实一直都觉得自己背包学得特别烂,今天开始补学背包

一、01背包

简介:顾名思义01背包就是~~01组成的背包~~对于每一件物品都只有两种状态，选或者不选。而每一件物品都有重量wei和价值val.,求如何装载使得不超过背包容量s而又能获得最大价值.很明显在没学背包之前,我们会想到搜索

int wei[MAXN],val[MAXN],s,n,ans=-1;//假设有n个物品,第i个重量为wei_i,价值为val_i,背包容量为s 
void dfs(int t,int wsum,int vsum)//wsum代表重量之和,vsum代表价值之和
{
if(wsum>s) return;
if(t==n+1) 
{
    ans=max(ans,vsum);
    return;
}
dfs(t+1,wsum,vsum);                //不选 
dfs(t+1,wsum+wei[i],vsum+val[i]);  //选 
}

当然，这样的时间复杂度是O(2^n), 嗯···TLE会制裁你的.

所以这个时候我们就用dp的方式.

基础启蒙(这一部分会快一点，因为重点不在这里)
$\ \ \ \ \ \ \ $很明显 $$ dp[i][j]=\left\{ \begin{aligned} dp[i-1][j](j<wei[i])\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]) \end{aligned} \right. $$ 所以板子就可以打出来了(以[$P1048$ 采药](https://www.luogu.com.cn/problem/P1048)为例) $\mathcal{CODE}
```
#include <iostream>
#include <cstdio>
using namespace std;
int wei[105],pri[105];
int dp[105][1005];
int main()
{
int t,m;
scanf("%d %d",&t,&m);
for(int i=1;i<=m;i++) scanf("%d %d",&wei[i],&pri[i]);
for(int i=1;i<=m;i++) 
{
    for(int j=1;j<=t;j++)  
    {
        if(j>=w[i]) dp[i][j]=max(dp[i-1][j-wei[i]]+pri[i],dp[i-1][j]);
        else dp[i][j]=dp[i-1][j];         
    }
} 
printf("%d",dp[m][t]);
return 0;
}
```
滚动数组压空间
$$dp[j]=max(dp[j],dp[j-wei[i]]+val[i])$$ $\ \ \ \ \ \ \ $我们注意到,$dp[j-wei[i]]+val[i]$的计算是依赖上一层(之前的$dp$式)的前面计算结果的，因为我们的更新依赖于前面，所以我们不能顺序遍历，否则它的更新就会出错。此时正确做法应该是倒序遍历。 $\mathcal{CODE}$(还是以[$P1048$ 采药](https://www.luogu.com.cn/problem/P1048)为例) ```cpp #include <cstdio> #include <algorithm> using namespace std; int dp[1005],wei[1005],val[1005]; int main() { int m,n; scanf("%d %d",&m,&n); for(int i=1;i<=n;i++) scanf("%d %d",&wei[i],&val[i]); for(int i=1;i<=n;i++) { for(int j=m;j>=wei[i];j--) dp[j]=max(dp[j],dp[j-wei[i]]+val[i]); } printf("%d",dp[m]); return 0; } ``` ### 二、$01$背包进阶 $\ \ \ \ \ \ \ 01$背包的板子虽然小清新，但是它的题往往会很毒瘤，这里举几个例子 $\ \ \ \ \ \ \ \ $ 1. 有一定限制 $\ \ \ \ \ \ \ \ $[题目](https://vjudge.net/problem/HDU-3466#author=0)传送门(讲真我找了好久)

$\ \ \ \ \ \ \ \ $对于每一个商人,我们可以想象出一个"东西难卖程度",即这个值越高的商人他的要求越高，那么这个商人的"东西难卖程度"可以这样定义:$need[i]-wei[i]$,"东西难卖程度"越高，我们越不可能去找他买东西。 $\ \ \ \ \ \ \ \ $所以我们把这个程度从小到大排序即可，然后就按它的限制做背包即可. > To Be Continued ### 三、完全背包 $\ \ \ \ \ \ \ \ $其实跟$01$背包没大差,只要我们想明白它也可以按照之前选过的情况来转移的话,核心代码就跟$01$只有顺序的区别了. ```cpp #include <cstdio> #include <algorithm> using namespace std; int dp[1005],wei[1005],val[1005]; int main() { int m,n; scanf("%d %d",&m,&n); for(int i=1;i<=n;i++) scanf("%d %d",&wei[i],&val[i]); for(int i=1;i<=n;i++) { for(int j=wei[i];j<=m;j++) dp[j]=max(dp[j],dp[j-wei[i]]+val[i]); } printf("%d",dp[m]); return 0; } ``` ### 四、完全背包进阶 >$\ \ \ \ \ \ \ $不想写了丢个链接吧:[戳我](https://www.luogu.com.cn/blog/1-2-1/loj-3182) ------------ 完结撒花❀❀❀ 等等,好像还有什么忘了? ------------ ### 五、二维费用背包 $\ \ \ \ \ \ \ \ $本来是没有讲的,但既然我们做了,那么还是讲一讲吧. >题目传送门:[$OJ$](http://222.180.160.110:1024/problem/7146) $\ \ \ \ \ \ \ \ $这道题我们可以发现它的限制有两个:忍耐度&杀怪数量,必须同时满足这两者才有可能升级. $\ \ \ \ \ \ \ \ $那我们可不可以换一个思路呢?我们把升级所需的$EXP$和杀怪的数量作为背包的容量,来转移最小的忍耐度消耗(其实我觉得这种做法应该是伪正解,正解应该还是以忍耐度和杀怪数量来转移)? $\ \ \ \ \ \ \ \ $与$01$背包类似,我们定义$dp[num][i][j]:$在前$num$只怪获得$i$经验值并杀掉了$j$只怪的最大经验值. $\ \ \ \ \ \ \ \ $与$01$&完全背包类似,这里我们可以压掉第一维,只需要用与$01/$完全背包类似的方式转移$wei$即可(我们把一只怪看成第二维$wei$为$1$的物品即可) $\ \ \ \ \ \ \ \ $需要注意的是,经验完全有可能一刀下去就超掉了升级所需,比如说,升级只需要$1Exp$,但是一刀$999$之类的,所以我们需要在原来经验的基础上加上一个不影响效率的小常数. $\ \ \ \ \ \ \ \ $$\mathcal{CODE}

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
struct node{
    ll exp,sta;
}mos[105];
ll dp[805][805];
int main() {
    ll n,m,k,s;
    while(~scanf("%lld %lld %lld %lld",&n,&m,&k,&s))
    {
        memset(dp,127,sizeof(dp));
        dp[0][0]=0;
        for(ll i=1;i<=k;i++) scanf("%lld %lld",&mos[i].exp,&mos[i].sta);    
        for(ll i=1;i<=k;i++)
        {
            for(ll j=mos[i].exp;j<=n+500;j++)
            {
                for(ll l=1;l<=s;l++) 
                {
                    dp[j][l]=min(dp[j][l],dp[j-mos[i].exp][l-1]+mos[i].sta);    
                }
            }
        }
        ll minn=1e9;
        for(ll i=1;i<=s;i++) 
        {
            for(int j=0;j<=500;j++) minn=min(minn,dp[n+j][i]);  
        }   
        if(minn<=m) printf("%lld\n",m-minn);
        else printf("-1\n");
    }
    return 0;
}