01背包专题（DP问题）

妖狐艹你老母 2023-07-11 08:40 36阅读 0赞

# 01背包的模板 #

小提醒：写01背包时要养成 **初始化数组** 和 **从1开始循环** 的习惯

## \#无优化 ##

for(int i=1;i<=n;i++)
    { 
        for(int c=1;c<=m;c++) //在这里，背包放入物品后，容量不断的减少，直到再也放不进了
        { 
            f[i][c]=f[i-1][c];
            if(c>=w[i])
            	f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]); // w为体积 v为价值
        }
    }
    // f[n][m]即为最大值（以物品为第一维数组）

## \#一维数组与判断条件优化 ##

for(int i=1;i<=n;i++)
    { 
        for(int c=m;c>=w[i];c--)
        { 
            f[c]=max(f[c],f[c-w[i]]+v[i]); // w为体积 v为价值
        }
    }
    // f[m]即为最大值（以容量为第一维数组）

# 经典例题1 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]  
**样例输入**

2
    50 1
    5
    10
    1 2 3 2 1 1 2 3 2 1
    50
    0

**样例输出**

-45
    32

**AC代码**

#include <iostream>
    #include <cstdio> 
    #include <algorithm>
    using namespace std;
    int n;
    int main()
    { 
        while(~scanf("%d",&n),n>0)
        { 
            int i,price[1005]= { 0},dp[1005] = { 0}; //dp要初始化为 0 
            for(i = 1; i<=n; i++)
                cin>>price[i];
            sort(price+1,price+1+n);
            int MAX=price[n];
            int j,m;
            cin>>m; //相当于背包容量
            if(m<5) //低于5元不能购买
            { 
                cout<<m<<endl;
                continue;
            }
            m-=5; //取出5元用于购买最贵的物品
            for(i = 1; i<n; i++)//01背包
            { 
                for(j = m;j>=price[i];j--)
                { 
                    dp[j] = max(dp[j],dp[j-price[i]]+price[i]);
                }
            }
            cout<<m+5-dp[m]-MAX<<endl;
        }
        return 0;
    }

**做法**：首先要在现在所拥有的余额中保留5元，用这五元去购买最贵的物品，而剩下的钱就是背包的总容量，将容量减为最小

--------------------

# 经典例题2 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]  
**样例输入**

2 
    10 1 
    20 1 
    3 
    10 1 
    20 2 
    30 1 
    -1

**样例输出**

20 10 
    40 40

**AC代码**

#include <iostream>
    #include <cstdio> 
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int val[5005]; //50 * 100 （不同设施的总数 * 设施的对应数量）
    int dp[100000];
    int main()
    { 
        int n,i,j,a,b,l,sum;
        while(~scanf("%d",&n),n>0)
        { 
            memset(val,0,sizeof(val));
            memset(dp,0,sizeof(dp));
            l = 0;
            sum = 0;
            for(i = 0;i<n;i++)
            { 
            	cin>>a>>b;
                while(b--)
                { 
                    val[l++] = a;
                    sum+=a;
                }
            }
            for(i = 0;i<l;i++) //相当于物品个数 
            { 
                for(j = sum/2;j>=val[i];j--) //sum/2 相当于背包容量 
                { 
                    dp[j] = max(dp[j],dp[j-val[i]]+val[i]);
                }
            }
            cout<<sum-dp[sum/2]<<' '<<dp[sum/2]<<endl; //前者一定大于后者
        }
        return 0;
    }

**做法**：换一种思维，因为题目要求要尽量平均分配，所以我们可以先将总价值 sum 求出，然后得出其分配的平均值为 sum/2，这个值即背包总容量，可以得出最小那个价值（因为01背包算出的最大值小于等于背包容量），所以另一个值即最大，用 sum 减去即可

--------------------

# 经典例题3 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]  
**样例输入**

1
    5 10
    1 2 3 4 5
    5 4 3 2 1

**样例输出**

**AC代码**

#include<iostream>
    using namespace std;
    struct Node
    { 
    	int val,vol;
    }node[1005];
    int main()
    { 
    	int t;
    	cin>>t;
    	while(t--)
    	{ 
    		int n,v,sum=0,i,j;
    		cin>>n>>v;
    		int dp[1005]={ 0};
    		for(int i=1;i<=n;i++)
    			cin>>node[i].val;
    		for(int i=1;i<=n;i++)
    			cin>>node[i].vol;
    		for(i=1;i<=n;i++)
    			for(j=v;j>=node[i].vol;j--)
    				dp[j]=max(dp[i],dp[j-node[i].vol]+node[i].val);
    		cout<<dp[v]<<endl;
    	}
    	return 0;
    }

01背包的原型题，只是用一个结构体替换了两个数组

--------------------

# 经典例题4 （很难） #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 3][]  
**样例输入**

3 
    5 10 2 
    1 2 3 4 5 
    5 4 3 2 1 
    5 10 12 
    1 2 3 4 5 
    5 4 3 2 1 
    5 10 16 
    1 2 3 4 5 
    5 4 3 2 1

**样例输出**

12 
    2 
    0

**AC代码**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
     
    struct Node
    { 
        int price;
        int val;
    } node[1005];
     
    int main()
    { 
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            int n,v,k,i,dp[1005][31] = { 0},a[31],b[31]; //dp[i][j]表示i体积下第j优解
            scanf("%d%d%d",&n,&v,&k); //骨头的数量,袋子的体积,第 K优解 
            for(i = 0; i<n; i++)
                scanf("%d",&node[i].price);
            for(i = 0; i<n; i++)
                scanf("%d",&node[i].val);
            int j;
            for(i = 0; i<n; i++)
            { 
                for(j = v; j>=node[i].val; j--)
                { 
                    int d;
                    for(d = 1; d<=k; d++) //分别将放入第 i个石头与不放第 i个石头的结果存入数组 a b 中
                    { 
                        a[d] = dp[j-node[i].val][d]+node[i].price;
                        b[d] = dp[j][d];
                    }
                    int x,y,z;
                    x = y = z = 1;
                    a[d]=b[d]=-1; //此 d 相当于 k+1, 即越界
                    while(a[x]!=-1||b[y]!=-1) //产生分歧后找到其中最大的 k的保留
                    { 
                        if(a[x] > b[y])
                            dp[j][z] = a[x++];
                        else
                            dp[j][z] = b[y++];
                        if(dp[j][z]!=dp[j][z-1]) //因为优解的值不能相同, 去掉重复了的优解
                        	z++;
                    }
                }
            }
            printf("%d\n",dp[v][k]);
        }
        return 0;
    }

**分析**：因为要求第k大，故不能有重复的解  
**做法**：将放或不放某一块石头分别存入数组中，最后**归并**从小到大排序进 dp 中，这样就可以存储特定体积下第 k 优解（最大价值），最后输出即可

--------------------

# 经典例题5（难） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 4]  
**样例输入**

3 
    0.04 3 
    1 0.02 
    2 0.03 
    3 0.05 
    0.06 3 
    2 0.03 
    2 0.03 
    3 0.05 
    0.10 3 
    1 0.03 
    2 0.02 
    3 0.05

**样本输出**

2 
    4 
    6

**AC代码**

#include<iostream>
    #include<cstring>
    using namespace std;
    int money[110]; //表示每个银行的钱（相当于背包容量） 
    double pp[110]; //被抓的概率 
    double dp[110*110];
    int main()
    { 
        int t;
        double p; //表示最大允许的概率
        int n; //计划的银行数
        cin>>t;
        while(t--)
        { 
            memset(dp,0,sizeof(dp));
            int sum=0;
            cin>>p>>n;
            for(int i=1;i<=n;i++)
            { 
                cin>>money[i]>>pp[i];
                sum+=money[i];
            }
            dp[0]=1; //以概率 1 为初始值 
            for(int i=1;i<=n;i++)
            { 
                for(int j=sum;j>=money[i];j--)
                { 
                    dp[j]=max(dp[j],(dp[j-money[i]])*(1-pp[i]));
                }
            }
            int ans=0;
            for(int j=0;j<=sum;j++) //包括一个银行都不能抢的情况 
            { 
                if((1-dp[j]-p)<1e-8) //卡一点精度，由于是double类型
                    ans=max(ans,j);
            }
            cout<<ans;
        }
        return 0; 
    }

**题目大意**：先给出几组数据，每组数据第一行是被抓的总概率 p (最后求得的总概率必须小于它，否则被抓)，然后是想抢的银行数 n 行，每行分别是该银行能抢的钱数 m \[ i \] 和被抓的概率 p \[ i \]，被抓的概率越大，逃跑概率越小，求最大逃跑概率  
**做法**：背包容量必然是钱数，然后是求最大逃跑概率，而题中每组数据第一行是被抓概率，所以要先用 1 减一下，还有最后求得的逃跑概率是随着抢银行的数量增加而减少，多抢一个银行，其钱数必将转化为概率的乘积，所以动态方程也要做出改变；最后遍历，剩余的钱数越多，说明所抢的钱数越少，逃跑几率越大，所以从大到小遍历背包容量，一旦大于 p，即为最大概率则跳出

--------------------

# 经典例题6（难） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 5]  
**样例输入**

2 10 
    10 15 10 
    5 10 5 
    3 10 
    5 10 5 
    3 5 6 
    2 7 3

**样例输出**

5 
    11

**AC代码**

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    struct node
    { 
        int p,q,v;
    }a[505];
    
    int cmp(node x,node y)//按 q-p排序，保证差额最小为最优
    { 
        return x.q-x.p<y.q-y.p;
    }
    
    int main()
    { 
        int n,m,i,j;
        int dp[5005]={ 0};
        while(~scanf("%d%d",&n,&m))
        { 
            for(i = 0; i<n; i++)
                cin>>a[i].p>>a[i].q>>a[i].v;
            memset(dp,0,sizeof(dp));
            sort(a,a+n,cmp);
            for(i = 0; i<n; i++)
            { 
                for(j = m; j>=a[i].q; j--) //剩余的钱大于 q 才能买
                { 
                    dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v); //减去 p
                }
            }
            cout<<dp[m];
        }
        return 0;
    }

**分析**：`dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v)` 表达的是这第 i 个物品要不要买，但同时也在判断第 i 个物品要不要先买，如果先买剩下的空间随便放，看是否得到的价值会更大  
**做法**：将物品按差值（q - p）进行排序，小的排在前面，然后就用01背包计算最高价值

--------------------

# 经典例题7 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 6]  
**样例输入**

200.00 3
    2 A:23.50 B:100.00
    1 C:650.00
    3 A:59.99 A:120.00 X:10.00
    1200.00 2
    2 B:600.00 A:400.00
    1 C:200.50
    1200.50 3
    2 B:600.00 A:400.00
    1 C:200.50
    1 A:100.00
    100.00 0

**样例输出**

123.50
    1000.00
    1200.50

**AC代码**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int dp[3000005]; //由于每张发票不超过 1000，最多 30 张，扩大 100 倍数后开这么大即可
     
    int main()
    { 
        char ch;
        double x,y;
        int sum,a,b,c,money[35],v;
        int t,i,j,k;
        while(~scanf("%lf%d",&x,&t),t)
        { 
            sum = (int)(x*100);//将小数化作整数处理
            memset(money,0,sizeof(money));
            memset(dp,0,sizeof(dp));
            int l = 0;
            for(i = 0; i<t; i++)
            { 
                cin>>k;
                a = b = c = 0;
                int flag = 1;
                while(k--)
                { 
                    scanf(" %c:%lf",&ch,&y);
                    v = (int)(y*100);
                    if(ch == 'A' && a+v<=60000)
                        a+=v;
                    else if(ch == 'B' && b+v<=60000)
                        b+=v;
                    else if(ch == 'C' && c+v<=60000)
                        c+=v;
                    else
                        flag = 0;
                }
                if(a+b+c<=100000 && a<=60000 && b<=60000 && c<=60000 && flag) //注意 flag
                    money[l++] = a+b+c; //仅添加有效发票
            }
            for(i = 0; i<=l; i++)
            { 
                for(j = sum; j>=money[i]; j--)
                        dp[j] = max(dp[j],dp[j-money[i]]+money[i]);
            }
            printf("%.2lf\n",dp[sum]/100.0);
        }
        return 0;
    }

**分析**：  
1、只有 a，b，c 三种物品可以报销，含有其他物品的发票作废  
2、每个物品的价值不能超过 600  
3、每张发票总价值不能超过 1000  
**做法**：  
先判断哪些发票可以报销，添加进 money 数组中，再对数组进行01背包求出最大报销金额

--------------------

# 经典例题8（非常难） #

**题目描述**  
DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包，每个人包的容量是相同的，都是 V  
可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。  
在 DD 看来，合理的背包安排方案是这样的：  
1、每个人背包里装的物品的总体积恰等于包的容量  
2、每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品  
3、任意两个人，他们包里的物品清单不能完全相同  
在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？  
**输入格式**  
第一行有三个整数：K，V，N （ k<=50 v<=5000 n<=200）  
第二行开始的 N 行，每行有两个整数，分别代表这件物品的体积和价值  
**输出格式**  
只需输出一个整数，即在满足以上要求的前提下所有物品的总价值的最大值  
**样例输入**

2 10 5
    3 12
    7 20
    2 4
    5 6
    1 1

**样例输出**

**AC代码**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    int n, v, k, c[205], w[205], q[55], ans = 0;
    int f[5005][55]; //背包容量 和 第 k优解 
    
    int main()
    { 
        cin>>k>>v>>n; //人数 背包容量 物品数
        memset(f, 128, sizeof(f)); f[0][1] = 0; //数组 f初始化越大越好且将f[0][1]初始化为 0
        for(int i=1;i<=n;i++) cin >> c[i] >> w[i];
        for(int i=1;i<=n;i++)
            for(int j=v;j>=c[i];j--)
    		{ 
                int now = 1, last = 1, cnt = 0;
                while(cnt < k) //不用去重（只要满足不同物品即可） 
    			{ 
                    if(f[j][now] > f[j-c[i]][last]+w[i])
                        q[++cnt] = f[j][now++];
                    else q[++cnt] = f[j-c[i]][last++]+w[i];
                }
                for(int z=1;z<=k;z++) f[j][z] = q[z];
            }
        for(int i=1;i<=k;i++) ans += f[v][i];
        cout<<ans;
        return 0;
    }

**分析**：与经典例题4 类似，但是求前 k 个最优解，所以不用去重  
**做法**：整体与经典例题4 类似，却采用了数组 f 初始化**越大越好** 且 将`f[0][1]`初始化为 0 的方法，没有记录放或不放物品的特解，而是直接将特解进行比较，从小到大存储在新的数组中，再最后遍历一遍将值重新赋回 **（目前暂未掌握，有待理解）**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200304203752426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200305073616685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200305083652743.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200305092730642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200306091822993.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200306132748266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200306143226128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70