前言

欢迎各位纠错

正文

背包问题,作为 DP 经典问题,也是 OIer 必须掌握的一门算法,一般有 01 背包,完全背包,多重背包。

01 背包

01 背包是背包中最简单也是最基础的,一般用 $w_i$ 表示第 $i$ 个物品的价值,$v_i$ 表示第 $i$ 个物品的体积,而 $f_{i,j}$ 表示放 $i$ 个物品时,容量为 $j$ 的背包所能达到的最大值,进而可以推出状态转移方程:$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})$。

然后就需要用到 DP 的常用操作,滚动数组优化,来看一段话:

由于对 $f_i$ 有影响的只有 $f_{i-1}$,可以去掉第一维,直接用 $f_j$ 来表示处理到当前物品时背包容量为 $i$ 的最大价值(by OI Wiki)。

所以状态转移方程就优化成了:$f_j=\max(f_j,f_{j-w_i}+v_i)$,又因为影响 $f_i$ 的只有 $f_{i-1}$,所以内循环要反过来。

附上 P1060 的代码:

#include <iostream>

using namespace std;
int n,m,v[1001],w[1001];
int dp[300001];

int main() {
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        cin>>v[i]>>w[i], w[i] *= v[i];
    }
    for (int i=1;i<=m;i++) {
        for (int j=n;j>=v[i];j--) {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[n];

完全背包

完全背包为 01 背包的变式,其变化在于,01 背包中每个物品只能拿一次,完全背包可以无限地拿,其他定义均可以参照 01 背包。

所以其状态转移方程为 $f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$(还有一个原始方程,但我太弱了推不出来)。

按照 01 背包的优化方式可优化为 $f_j=\max(f_j,f_{j-w_i}+v_i)$,是不是一脸懵,这不是 01 背包的吗,但别忘了,01 背包的内循环是反的(因为要保证前面没有被拿过),而完全背包可以拿无限次所以要付出最小的代价,所以,要从前往后推,也就是内循环正过来。

附上 P1616 代码:

#include<iostream>
#include<cstdio>  

using namespace std;
long long n,m,w[10011],c[10011],dp[10000010];

int main(){
    scanf("%lld%lld",&m,&n);
    for (int i=1;i<=n;i++) {
        scanf("%lld%lld",&w[i],&c[i]);
    }
    for (int i=1;i<=n;i++) {
        for (int j=w[i];j<=m;j++) {
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    printf("%lld",dp[m]);
}

多重背包

先来看一句话:

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 $k$ 个,而非一个。一个很朴素的想法就是:把「每种物品选 $k$ 次」等价转换为「有 $k$ 个相同的物品,每个物品选一次」(by OI Wiki)。

所以其状态转移方程为:$\max \limits^{k_i}_ {k=0}(f_{i-1,j-k \times w_j}+v_i \times k_i) $,时间复杂度为 $O(W\sum_{i=1}^nk_i)$。

$finally$

背包的做法还有很多,但由于篇幅限制,我就不一一放出来了。

分类: 文章

Evol_Yester_Nt

抽紫烟,吸纯氧,健康生活everyday

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code