【dp】 背包问题

问题一：01背包

题目：

【题目描述】

一个旅行者有一个最多能装 M 公斤的背包，现在有 n件物品，它们的重量分别是W1，W2，...,Wn它们的价值分别为C1,C2,...,Cn求旅行者能获得最大总价值。

【输入】

第一行：两个整数，MM(背包容量，M≤200)和NN(物品数量，N≤30)；

第2..N+12..N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

12

这类问题就是01背包问题，是dp背包中的最简单的一种

状态转移方程：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])

即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]（来自百度）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int f[][],c[],w[],m,n;
int main() {
    cin>>m>>n;
    for(int i=; i<=n; ++i) {
        cin>>w[i]>>c[i];
    }
    for(int i=; i<=n; ++i) {
        for(int v=m; v>; v--) {
            if(w[i]<=v) {
                f[i][v]=max(f[i-][v],f[i-][v-w[i]]+c[i]);
            } else {
                f[i][v]=f[i-][v];
            }
        }
    }
    cout<<f[n][m];
    return ;

}

问题来了开一个二维数组是不是有点浪费空间（想想蛇形填数那个题，二维数组开不到那么大，就GG了）所以只需要用f[v]表示重量不超过v的最大价值就OK了

f[i]=max(f[v],f[v-c[i]]+w[i])

为什么可以从二维变成一维的呢？

因为f[i][v]是从f[i-1][v],f[i-1][v-c[i]]+w[i])得出的，当我将v从m开始向前枚举时，每次都会更新当前的第i个物体的更新，只依赖于第i-1个的物体的结果所以可以用滚动数组，每次只存i和i-1时候的值  第i个物体在容积为j状态的更新，只依赖i-1物体容量里j-w[i]的状态的结果所以，从后面开始向前更新，则求j位置时候，j-w[i]的值依旧为i-1时候的值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int f[],c[],w[],m,n;
int main() {
    cin>>m>>n;
    for(int i=; i<=n; ++i) {
        cin>>w[i]>>c[i];
    }
    for(int i=; i<=n; ++i) {
        for(int v=m; v>; v--) {
            if(w[i]<=v) {
                f[v]=max(f[v],f[v-w[i]]+c[i]);
            } else {
                f[v]=f[v];
            }
        }
    }
    cout<<f[m];
    return ;

}

01背包为什么枚举v时要逆序？

为了避免要使用的子状态收到影响。（很重要!）

问题二：完全背包

【题目描述】

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

【输入】

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；

第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

max=12

特点：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

[思路]：这个问题非常类似于01背包，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……。仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程:

f[i][j] = max{f[i][j],f[i-1][j - k * c[i]] + k * w[i]}(0<=k*c[i]<=v)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int w[],c[],f[][],m,n;
int main() {
    cin>>m>>n;
    for(int i=; i<=n; ++i) {
        cin>>w[i]>>c[i];
    }
    for(int i=; i<=n; ++i) {
        for(int v=; v<=m; ++v) {
            if(v<w[i]) {
                f[i][v]=f[i-][v];
            } else {
                if(f[i-][v]>f[i][v-w[i]]+c[i]) {
                    f[i][v]=f[i-][v];
                } else {
                    f[i][v]=f[i][v-w[i]]+c[i];
                }
            }
        }
    }
    cout<<"max="<<f[n][m];
    return ;
}

同上，和01背包一样开二维数组浪费空间

注意v要从前往后枚举，为什么?

 在01背包问题里面，我们逆序遍历V是为了保证f[i]始终是i-1物品推出的，从而保证每种物品只用一次。而完全背包问题里面我们就可以正序遍历，这样就可以在一次遍历f[V]中考虑第i种物品的所有拿法。至于为什么这样就能求出所有的，我会在明天做一个解释

解释开始：因为第i种物品一旦出现，原来没有第i种物品的情况下可能有一个最优解，现在第i种物品 出现了，而它的加入有可能得到更优解，所以之前的状态需要进行改变，故需要正序。

直接用一组例子来解释：
样例：

运行过程f数组内：

0

0　　0　

0　　0　　0　

0　　0　　1　　0

0　　0　　1　　1　　0

0　　0　　1　　1　　2　　0

0　　0　　1　　1　　2　　2　　0

0　　0　　1　　1　　2　　2　　3　　0

0　　0　　1　　1　　2　　2　　3　　3　　0

0　　0　　1　　1　　2　　2　　3　　3　　4　　0

0　　0　　1　　1　　2　　2　　3　　3　　4　　4　　0

0　　0　　1　　1　　2　　2　　3　　3　　4　　4　　5　　0

0　　0　　1　　3　　2　　2　　3　　3　　4　　4　　5　　0

0　　0　　1　　3　　3　　2　　3　　3　　4　　4　　5　　0

0　　0　　1　　3　　3　　4　　3　　3　　4　　4　　5　　0

0　　0　　1　　3　　3　　4　　6　　3　　4　　4　　5　　0

0　　0　　1　　3　　3　　4　　6　　6　　4　　4　　5　　0

0　　0　　1　　3　　3　　4　　6　　6　　7　　4　　5　　0

0　　0　　1　　3　　3　　4　　6　　6　　7　　9　　5　　0

0　　0　　1　　3　　3　　4　　6　　6　　7　　9　　9　　0

0　　0　　1　　3　　5　　4　　6　　6　　7　　9　　9　　0

0　　0　　1　　3　　5　　5　　6　　6　　7　　9　　9　　0

0　　0　　1　　3　　5　　5　　6　　8　　7　　9　　9　　0

0　　0　　1　　3　　5　　5　　6　　8　　10　　9　　9　　0

0　　0　　1　　3　　5　　5　　6　　8　　10　　10　　9　　0

0　　0　　1　　3　　5　　5　　6　　8　　10　　10　　11　　0

0　　0　　1　　3　　5　　5　　6　　8　　10　　10　　12　　0

liuzitong大佬的解释：

背包容量为5

有1个物品,体积为2,价值为3(这么简单的例子不是因为我懒)

从5开始呢?

f[5]=f[5-2]+3;

f[4]=f[4-2]+3;

f[3]=f[3-2]+3;

f[2]=f[2-2]+3;

1和0不行

可以看出,从5到2,关系分别是

由3推5

由2推4

由1推3

由0推2

从一开始推出来的5开始没有被用过的再被利用

从1开始呢?

1和0不行

f[2]=f[2-2]+3;

f[3]=f[3-2]+3;

f[4]=f[4-2]+3;

f[5]=f[5-2]+3;

可以看出,从5到2,关系分别是

由0推2

由1推3

由2推4

由3推5

可以看出:

由0推出的2又在推4的时候用到了,这就实现了完全背包

最终答案就是12（wc写死我了，好多啊）

如有bug请评论指明。

优化代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int w[],c[],f[],m,n;
int main() {
    cin>>m>>n;
    for(int i=; i<=n; ++i) {
        cin>>w[i]>>c[i];
    }
    for(int i=; i<=n; ++i) {
        for(int v=w[i]; v<=m; ++v) {//注意v从w[i]开始枚举也可从1开始枚举
            if(f[v-w[i]]+c[i]>f[v])
                f[v]=f[v-w[i]]+c[i];
        }
    }
    cout<<"max="<<f[m];
    return ;
}

问题三：多重背包

【题目描述】

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

【输入】

第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中v≤100，w≤1000，s≤10。

【输出】

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

【输入样例】

【输出样例】

特点：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

转化为01背包问题：

朴素方法：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度是O(V*Σn[i])。 Σ表示把n[i]加起来，就是说两层循环的复杂度

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int v[],w[],s[],f[],n,m;
int main() {
    cin>>n>>m;
    for(int i=; i<=n; ++i) {
        cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=; i<=n; ++i) {//枚举i
        for(int j=m; j>=; j--) {//枚举空间（容量）
            for(int k=; k<=s[i]; ++k) {//枚举选的数量
                if(j-k*v[i]<)
                    break;//装不下了就退出
                else {
                    f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
                }
            }
        }
    }
    cout<<f[m];
    return ;
}

优化版：

利用二进制拆分。复杂度O(VΣlog n[i])

考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。（来自一本通）

拆分过程：

cin>>x>>y>>z;
        while(z>=sum) { //sum是指数
            v[++len]=x*sum;
            w[len]=y*sum;
            z-=sum;
            sum*=;
        }
        v[++len]=x*z;
        w[len]=y*z;

完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar();
    int x = , f = ;
    while(c < '' || c > '') {
        if(c == '-') f = -;
        c = getchar();
    }
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int v[],w[],s[],f[],n,m;
int main() {
    cin>>n>>m;
    int len=;
    for(int i=; i<=n; ++i) {
        int x,y,z;
        int sum=;
        /*x是价格，y是价值,z是数量*/
        cin>>x>>y>>z;
        while(z>=sum) { //sum是指数
            v[++len]=x*sum;
            w[len]=y*sum;
            z-=sum;
            sum*=;
        }
        v[++len]=x*z;
        w[len]=y*z;
    }
    for(int i=; i<=len; ++i) {
        for(int j=m; j>=v[i]; j--) {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return ;
}

问题四：分组背包

问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[v]表示前k组物品花费费用v能取得的最大价值

for 所有的组k
    for v=V..
        for 所有的i属于组k
　　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]}

注意这里的三层循环的顺序，“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

题目

P1757 通天之分组背包

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
#define MAXN 1005
using namespace std;
const int maxn=;
const int minn=-;
inline int read() {
    char c = getchar(); int x = , f = ;
    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();
    return x * f;
}
int a[MAXN][MAXN],f[MAXN],c[MAXN],w[MAXN],sum[MAXN];
int main()
{
    int n,m;
    cin>>m>>n;
    int zu=;
    for(int i=;i<=n;++i)
    {
        int p;
        cin>>w[i]>>c[i]>>p;
        sum[p]++;
        zu=max(zu,p);
        a[p][sum[p]]=i;
    }
    for(int i=;i<=zu;++i)
    {
        for(int j=m;j>=;--j)
        {
            for(int k=;k<=sum[i];++k)
            {
                if(j>=w[a[i][k]])
                f[j]=max(f[j],f[j-w[a[i][k]]]+c[a[i][k]]);
            }
        }
    }
//    cout<<f[m];
    int ans=f[m];
    cout<<ans;//ac
    return ;
}

问题五：有依赖的背包问题

例题：

P1064 金明的预算方案

 

思路：

这类问题是01背包的变形。所有的物品分为两类，一类是主件，另一类是附件，每一个附件都有它的主件，选取它的主件之后才能选取附件。

详见：我的另一篇博客