背包九讲

背包九讲一般的背包问题: 每种物品有一个价格W和体积V,你现在有一个容积为V的背包。问你怎么装使背包的价值和最大。 01背包 多种物品,每个物品只有一个,求能或得的最大总价值。 如果我们不选第i件物品,那我们就相当于用 i-1 件物品,填充了体积为V的背包所得到的最优解。 当我们选第i件物品时,就相当于用i

一般的背包问题:

每种物品有一个价格W和体积V,你现在有一个容积为V的背包。问你怎么装使背包的价值和最大。

01背包

多种物品,每个物品只有一个,求能或得的最大总价值。

如果我们不选第i件物品,那我们就相当于用 i-1 件物品,填充了体积为V的背包所得到的最优解。

当我们选第i件物品时,就相当于用i-1的物品,填充v – c[i]/的背包所得到的最优解。

背包九讲

用f[i][v]表示用i件物品填充体积为V的背包所得到的价值。

那么方程式就是:

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

一维的就是

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

显而易见,我们f[j] 只会被以前的状态影响。

如果我们顺序枚举,就可能会被前面的状态影响掉。

那我们考虑倒叙枚举,这样f[j] 不会被之前的状态影响,且我们更新的话也不会影响其他位置的状态

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;  5 int f[1001],w[1001],v[1001];  6 int main(){  7     int n,m;  8     scanf("%d%d",&n,&m);  9     for(int i = 1;i <= n; i++){ 10         scanf("%d%d",&w[i],&c[i]); 11  } 12     for(int i = 1; i <= n; i++){ 13         for(int j = m; j >= w[i]; j--){ 14             f[j] = max(f[j],f[j-w[i]]+v[i]); 15  } 16  } 17     prinf("%d",f[m]); 18     return 0; 19 } 

水题——>采药

完全背包

每个物品有无限个,可重复选取;

转移方程就是

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

跟01背包类似,我们可以把它给成一维的,只不过要正着枚举。

1     for(int i = 1;i <= n; i++){ 2         for(int j = w[i]; j <= m; j++){ 3             f[j] = max(f[j] , f[j-w[i]]+v[i]); 4  } 5     }

多重背包

跟01背包类似,只不过他每种物品有k个,而不是1个

1.转化为01背包

 我们可以把每件物品选k次,转换为有k个相同的物品,每个物品选一次

然后就可以套用01背包

时间复杂度O(nwΣki)

2.二进制优化

我们仍考虑转化为01背包 ,我们可以对k的拆分入手

对于一个数k 可以根据二进制拆成2^j相加的形式。

但我们要保留1个物品,然后在对其他的k-1个进行拆分

例如

  1. 6 = 1 + 2 + 3
  2. 8 = 1 + 2 + 4 +1
  3. 18 = 1 + 2 + 4 + 8 + 3
  4. 31 = 1 + 2 + 4 + 8 +16
背包九讲背包九讲

 1 cnt = 0;//当前的物品数
 2 for(int i = 1; i <= m; i++){  3     int c = 1;  4     scanf("%d%d",&p,&vv,&k);  5     while(k - c > 0){//打包k-1个物品
 6           k -= c;  7           w[++cnt] = c * p;  8           v[cnt  = c * vv;  9            c *= 2; 10  } 11     w[++cnt] = p * k;//打包剩下的那1个物品
12     v[cnt] = k * vv; 13 }

二进制拆分

另一种方法

1     for(int i = 1; i <= n; i++){ 2         scanf("%d%d%d",&val,&p,&k); 3         for(int j = 1; j <= k; j<<=1){ 4             k -= j; 5             v[++cnt] = j * p; 6             w[cnt] = j * val; 7  } 8         if(k != 0) v[++cnt] = k * p,w[cnt] = k * val; 9     

3.单调队列优化

 我不会QAQ,但也不常考。

有兴趣的可以看一下链接

习题 : P1776  宝物筛选

 

背包九讲
背包九讲

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,m,p,val,k,cnt = 1;
 6 int w[1000100],v[1000100],f[1000100];
 7 int main(){
 8     scanf("%d%d",&n,&m);
 9     for(int i = 1; i <= n; i++){
10         scanf("%d%d%d",&val,&p,&k);
11         for(int j = 1; j <= k; j<<=1){
12             k -= j;
13             v[++cnt] = j * p;
14             w[cnt] = j * val;
15         }
16         if(k != 0) v[++cnt] = k * p,w[cnt] = k * val;
17     }
18     for(int i = 1; i <= cnt; i++){
19         for(int j = m; j >= v[i]; j--){
20             f[j] = max(f[j],f[j-v[i]] + w[i]); 
21         }
22     }
23     printf("%d\n",f[m]);
24     return 0; 
25 }

宝物筛选

 

 

 

二维费用背包

例题 P1855 榨取kkksco3(普及减的水题)

很明显的01背包问题,但选一个物品会消耗两种价值。

我们可以考虑再开一维数组,同时转移两个价值(其他背包同理)

但不能够再开一维数组存物品编号,因为容易MLE

1 for (int k = 1; k <= n; k++) { 2   for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
3     for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
4       dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1); 5 }

三倍经验

  1. L国的战斗之间谍
  2. NASA的食物计划

分组背包

水题 ——> P1757 通天之分组背包

就是讲物品分组,每组物品只能选一个。

我们可以把在所有物品中选一件,变成从当前组中选一件,直接跑01背包就okk了

1 for (int k = 1; k <= ts; k++)          // 循环每一组
2   for (int i = m; i >= 0; i--)         // 循环背包容量
3     for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
4       if (i >= w[t[k][j]]) 5         dp[i] = max(dp[i],  dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

进阶:P3961 黄金矿工

我们可以一次求出每条直线的斜率,在排个序(方便判断斜率是否相等)

相等的分在一组物品中,再跑一遍01背包就AC了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;  5 int n,T,cnt,maxn;  6 int t[210][210],v[210][210],num[210];  7 int f[40010];  8 struct node{  9     int x,y,v,t; 10     double k; 11 }e[210]; 12 int comp(node a,node b){ 13     if(a.k == b.k) return a.y < b.y; 14     return a.k < b.k; 15 } 16 int main(){ 17     scanf("%d%d",&n,&T); 18     for(int i = 1; i <= n; i++){ 19         scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].t,&e[i].v); 20         e[i].k = e[i].y *(1.0) / e[i].x * (1.0);//求斜率
21  } 22     sort(e+1,e+n+1,comp);//排序
23     for(int i = 1; i <= n; i++){ 24         if(e[i].k != e[i-1].k || i == 1) {//找到一条斜率不同的直线
25             cnt++; 26  } 27         if(num[cnt] == 0){//第一件物品
28             num[cnt]++; 29             t[cnt][1] = e[i].t; 30             v[cnt][1] = e[i].v; 31  } 32         else{//其他物品
33             num[cnt]++; 34             t[cnt][num[cnt]] = t[cnt][num[cnt]-1] + e[i].t; 35             v[cnt][num[cnt]] = v[cnt][num[cnt]-1] + e[i].v; 36  } 37  } 38     f[0] = 0; 39     for(int i = 1; i <= cnt; i++){//分组背包
40         for(int j = T; j >= t[i][1]; j--){ 41             maxn = f[j]; 42             for(int k = 1; k <= num[i]; k++){ 43                 if(j > t[i][k]){ 44                     maxn = max(maxn,f[j-t[i][k]] + v[i][k]); 45  } 46  } 47             f[j] = maxn; 48  } 49  } 50     printf("%d",f[T]); 51     return 0; 52 } 

有依赖的背包(树形背包)

例题——>金明的预算方案

我们称不依赖别的物品的为主件,依赖于于其他物品的为附件;

包含一个主件和若干个附件有一下可能;

  1. 只选附件
  2. 选完主件后再选一个附件
  3. 选完主件后再选两个附件
  4. 。。。。。

可以将这几种可能性转换为一件物品,因为这几种可能性只能选一种,最后在跑一边分组背包

如果是多叉树的集合,先算子节点的集合,最后再算父亲节点的集合。

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<iostream>
 4 using namespace std;  5 int n,m,c,p,q,t;  6 int w[65][3],v[65][3],f[65][3200];  7 int main(){  8     scanf("%d%d",&n,&m);  9     n/=10; 10     for(int i = 1; i <= m; i++){ 11         scanf(“%d%d%d”,&c,&p,&q); 12         c = c/10; 13         if(q == 0){//主件
14             w[i][0] = c; 15             v[i][0] = c*p; 16  } 17         else if(w[q][1] == 0){//第一件附件
18             w[q][1] = c; 19             v[q][1] = c*p; 20  } 21         else {//第二件附件
22             w[q][2] = c; 23             v[q][2] = c*p; 24  } 25  } 26     for(int i = 1; i <= m; i++){ 27         for(int j = 0; j <= n; j++){ 28             f[i][j] = f[i-1][j];//一个都不选的情况
29             if(j >= w[i][0]){//选主件的情况
30                 t = f[i-1][j-w[i][0]] + v[i][0]; 31                 if(t > f[i][j]){ 32                     f[i][j] = t; 33  } 34  } 35             if(j >= w[i][0]+w[i][1]){//选主件和第一个附件的情况
36                 t = f[i-1][j-w[i][0]-w[i][1]] + v[i][0]+v[i][1]; 37                 if(t > f[i][j]){ 38                     f[i][j] = t; 39  } 40  } 41             if(j >= w[i][0]+w[i][2]){//选主件和第二个附件的情况
42                 t = f[i-1][j-w[i][0]-w[i][2]] + v[i][0]+v[i][2]; 43                 if(t > f[i][j]){ 44                     f[i][j] = t; 45  } 46  } 47             if(j >= w[i][0]+w[i][1]+w[i][2]){//选主件和所有附件的情况
48                 t = f[i-1][j-w[i][0]-w[i][1]-w[i][2]] + v[i][0]+v[i][1]+v[i][2]; 49                 if(t > f[i][j]){ 50                     f[i][j] = t; 51  } 52  } 53  } 54  } 55     cout<<f[m][n]*10<<endl; 56     return 0; 57 }

 树形背包(进阶)

一般的形式就是 给定一个n个节点的点权树,要求你从中选出m个节点,使这些选出的节点点权和最大,一个节点

能被选择时,当且仅当父亲节点被选择时、

O(n^3)解法

考虑 f[u][i] 表示在u的子树中,选择i个节点(包括他本身的贡献)则方程式为

 1 f[u][i] = max(f[u][i]+f[v][i-j] + d[v] 

其中d[v] 表示v的点权,i-j表示在子树中选i-j个节点

例题——选课

 f[i][j] 表示在i的子树中选j个能得到的最大的学分。 一个要注意的点是,我们开了一个虚拟节点,那么我们在统计答案是应该是f[0][m+1] 而不是f[0][m],因为我们这个节点算上去。

转移方程直接套用上面的就行了。

附上完整代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;  5 int n,m,ans,tot,k;  6 int head[310],f[310][310],size[310];//f[i][j] 表示在i的子树中选j个物品所得到的最大的学分数 
 7 struct node  8 {  9     int to; 10     int net; 11 }e[10100]; 12 void add(int x,int y) 13 { 14     tot++; 15     e[tot].to = y; 16     e[tot].net = head[x]; 17     head[x] = tot; 18 } 19 void dp(int x,int fa){ 20     size[x] = 1; 21     for(int i = head[x]; i; i = e[i].net) 22  { 23         int  to = e[i].to; 24         if(to == fa) continue; 25  dp(to,x); 26         for(int j = m+1; j >= 1; j--)//枚举x的子树中选j个物品 
27  { 28             for(int k = 0; k < j; k++)//枚举在 to的子树中选k个物品 
29  { 30                 f[x][j] = max(f[x][j] , f[x][j-k] + f[to][k]); 31  } 32  } 33  } 34 } 35 int main(){ 36     scanf("%d%d",&n , &m); 37     for(int i = 1; i <= n; i++) 38  { 39         scanf("%d%d",&k , &f[i][1]); 40  add(k,i); 41  } 42     dp(0 , 0); 43     printf("%d\n", f[0][m+1]); 44     return 0; 45 }

背包求方案数

给定一个背包容量,物品费用,和其他关系,求装到一定容量的方案数

这种问题把求最大值改为求和就ok了

 1 dp[i] = Σ(dp[i] ,dp[i-c[i]) 

初值 dp[o] = 1;

因为 当容量为0时:一种方案为什么也不装。

背包输出方案数

我们用g[i][v] 表示体积为V时第i件物品选没选。

int v = V;  // 记录当前的存储空间
for (
    从最后一件循环至第一件)  // 因为最后一件物品存储的是最终状态,所以从最后一件物品进行循环
{
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

 

背包前k优解

裸题——>多人背包

这道题,我们可以对n件物品求一个01背包,然后k个人取前k优解就是答案。

那么我们考虑怎么求前k优解

我们设 f[i][j][k] 表示用i件物品,花费j的体积,得到的第k优解

那么我们观察一下原来的转移方程

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

我们可以发现 f[i][v] 只能由 f[i-1][v] , f[i-1][v-c[i]] + w[i] 转移过来,那么前k优解一定存在于着f[i-1][v][1~k] 以及f[i-1][v-c[i]][1~k] + w[i]当中。

我们可以把这·f[i-1][v]的前k优解 和 f[i-1][v-c[i]]+w[i] 抽象成两个队列,

那么这两个队列肯定是两个单调队列,因此,我们参考归并排序的思想,去这两个队列的前k大,那么这前k大的数,就是f[i][v]的前k优个解

但考虑到三维数组肯定会MLE,因此我们可以像01背包那样抹去第一维。

那么最后的代码就是

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int k,V,n,ans;
int v[255],w[255],f[5010][55],now[55];
inline int read()
{
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch-'0'; ch = getchar();}
    return s * w;
}
int main()
{
    k = read(); V = read(); n = read();
    for(int i = 0; i <= V; i++) for(int j = 0; j <= k; j++) f[i][j] = -2333333;//初始化
    for(int i = 1; i <= n; i++)
    {
        v[i] = read(); w[i] = read();
    }
    f[0][1] = 0;//零体积的最优解为0
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= v[i]; j--)
        {
            int a1 = 1, b1 = 1,cnt = 0;//a1,b1分别为两个队列的队头,cnt为当前选了几个数即第k优解
            while(cnt <= k)
            {
                if(f[j][a1] > f[j-v[i]][b1] + w[i])//选第一个队列的队头的时候
                {
                    now[++cnt] = f[j][a1];
                    a1++;
                }
                else//选另一个队列队头的时候
                {
                    now[++cnt] = f[j-v[i]][b1] + w[i];
                    b1++;
                }
            }
            for(int u = 1; u <= k; u++) f[j][u] = now[u];//now存当前的第k优解
        //    for(int u = 1; u <= k; u++) cout<<now[u]<<endl;
        }
    }
    for(int i = 1; i <= k; i++) ans += f[V][i];
    printf("%d\n",ans);
    return 0;
} 

 

不懂得童鞋出门右转 ——> 顾Z大佬的背包九讲

例题 ——>P3983 赛斯石

这个题最大的难点在于物品可以拆开,但船不能拆

如载重7的船,可以装4si和3si 也可以装1si和6si

所以 1-10载重船的最大利益可以用背包求出来;

最后选一些船走,船的收益已固定,可以跑完全背包求质量为n的最大收益

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;  5 long long n,b[15],v[15],w[15];  6 long long ans[100010];  7 long long a[12] = {0,1,3,5,7,9,10,11,14,15,17};  8 int main(){  9     scanf("%ld",&n); 10     for(int i = 1; i <= 10; i++){ 11         scanf("%ld",&b[i]); 12         v[i] = i; 13  } 14     for(int i = 1; i <= 10; i++){//每条船的收益 
15         for(int j = i; j <= 10; j++){ 16             w[j] = max(w[j],w[j-i] + b[i]); 17  } 18  } 19     for(int i = 1; i <= 10; i++) w[i] -= a[i];//利润 
20     ans[0] = 0; 21     for(int i = 1; i <= 10; i++){//怎样租船利润最大 
22         for(int j = v[i]; j <= n; j++){ 23             ans[j] = max(ans[j] , ans[j- v[i]] + w[i]); 24  } 25  } 26     printf("%ld",ans[n]); 27     return 0; 28 } 

例2 背包dp

我们第一次想可能会想到 f[m] 表示 达到m种方案的最少钱数,跑一边多重背包,可是一看m的范围,完了炸了,数组开不了10^17那么大

那我们换一种思路f[i][j]  表示用i件物品 花费j个Q币能达到的方案数。那这不就相当于一个分组背包了吗?

为什么呢? 我们可以把它当成有n组,每组可以选1-num[i] 种情况,但每种情况只能选1次

所以我们可以推出方程式来

1 f[i][j] = max(f[i][j] , f[i-1][j-p[i]*k] * k

p[i]表示第i个物品买一个要花多少钱,k表示你选了多少件物品

我们在想一下,二维的开不了这么大,那我们可以像背包那样抹去第一维,给他来个滚动数组

于是有了下面的方程

 1 f[j] = max(f[j] , f[j-p[i]*k] * k) 

最后一定要注意的点是,要开long long 不然你就会炸

背包九讲
背包九讲

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 #define LL long long
 6 LL n,m,tot;
 7 LL num[1000100],p[1000100],f[1000100];//不开long long 两行泪
 8 int main(){
 9     scanf("%lld%lld",&n,&m);
10     for(LL i = 1; i <= n; i++) scanf("%lld",&num[i]);//每组最多选几个
11     for(LL i = 1; i <= n; i++){
12         scanf("%lld",&p[i]);//每件物品的价钱
13         tot += p[i] * num[i];//计算最大花多少钱
14     } 
15     f[0] = 1;
16     for(LL i = 1; i <= n; i++){//枚举组数
17         for(LL j = tot; j >= p[i]; j--){//枚举体积
18             for(LL k = 1; k <= num[i]; k++){//枚举每组选几个
19                 if(p[i] * k <= j)  f[j] = max(f[j] , f[j-p[i]*k] * k);
20             }
21         }
22     }
23     for(LL i = 0; i <= tot; i++){//找到第一个大于等于m的方案数
24         if(f[i] >= m){
25             printf("%lld\n",i);
26             return 0;
27         }
28     }
29 } 

完整代码

 

例三: 粉刷匠

我们可以维护两个数组 f[i][j][k] 表示第i个木块,刷k次,刷前j块,能刷对的最大格子数

                                   g[i][j]  表示 前i个木块,刷k次能刷对的最大格子数。

那么f数组怎么转移呢

我们考虑枚举每次刷的起点s 那么从s刷到j的贡献就是从s到j 1的个数 和0的个数取个max

那么方程就可以写成

 1 f[i][j][k] = max(f[i][j][k] , f[i][s-1][k-1]+calc(i , s ,j)); 

因为每个点最多被刷一次,所以要从s-1开始枚举

这是我们想象,我们得到了一些刷着颜色段的木块,每一块木板有k种选择,可以刷1次或2次或。。。。,但每种情况只能选一种。(那这不就是妥妥的分组背包吗 QAQ

对于每种情况,他们的体积是他们要粉刷的次数,他们的贡献就是f[i][m][k] 一共有n组,这样我们就可以套用分组背包来求。

最后附上代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;  5 int n,m,t;  6 int sum[55][55],a[55][55];  7 int f[55][55][55],dp[55][2510];  8 int calc(int i,int s,int j)//计算涂一还是涂零的分多 
 9 { 10     return max(sum[i][j] - sum[i][s-1],j-s+1 -sum[i][j] + sum[i][s-1]); 11 } 12 int main(){ 13     scanf("%d%d%d",&n,&m,&t); 14     for(int i = 1; i <= n; i++) 15  { 16         for(int j = 1; j <= m; j++) 17  { 18             scanf("%1d",&a[i][j]); 19             sum[i][j] = sum[i][j-1] + a[i][j];//维护一个前缀和
20  } 21  } 22     for(int i = 1; i <= n; i++)//枚举每个木板 
23  { 24         for(int j = 1; j <= m; j++)//枚举前几块
25  { 26             for(int k = 1; k <= m; k++)//枚举涂多少次 ,每块木板最多涂m次
27  { 28                 for(int s = 1; s <= j; s++)//枚举从哪开始涂 
29  { 30                     f[i][j][k] = max(f[i][j][k] , f[i][s-1][k-1]+calc(i , s ,j)); 31  } 32  } 33  } 34  } 35     for(int i = 1; i <= n; i++)//枚举每块木板 (每组)
36  { 37         for(int j = t; j >= 1; j--)//枚举体积 
38  { 39             for(int k = 0 ; k <= min(j,m); k++)//枚举涂多少次 ,但要保证k小于总共要涂得个数
40  { 41                 dp[i][j] = max(dp[i][j] , dp[i-1][j-k] + f[i][m][k]); 42  } 43  } 44  } 45     printf("%d\n",dp[n][t]); 46     return 0; 47 }

 

今天的文章背包九讲分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/56439.html

(0)
编程小号编程小号
上一篇 2023-08-26
下一篇 2023-08-26

相关推荐

发表回复

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