D（背）P（包）专题

ACM DP 干货
​ ShengRang && Thea.R

​ 2016.07.11

01背包

模型：每个物品体积为vi，价值为wi，选择任意件物品放入容量为m的背包内，求可以取得的最大价值

方程：f[i][j]表示i个物品放入容量为j的背包所能取得的最大价值

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

空间优化：

    for(int i=1; i<=n; i++)
        for(int j=m; j>=v[i]; j—)  //从大到小转移
        　f[j]=max(f[j], f[j-v[i]]+w[i]);

POJ 2923 Relocation

http://poj.org/problem?id=2923

【Description】

给定n(<=10)个物品, 重量w[i] (<=100).
有两辆车, 容量为C1, C2(<=100). 每次两辆车一起运输一些家具.每辆车运的家具重量和不大于容量.
求运完所有家具至少要几次运送.

【Sample Input】

2
6 12 13 # 6个物品, C1=12, C2=13
3 9 13 3 10 11 # 重量
7 1 100 # 7个物品, C1=1, C2=100
1 2 33 50 50 67 98

【Sample Output】

Scenario #1:
2 # (9+3, 13), (11, 10+3)
Scenario #2:
3

n比较小可以状压.
先对所有状态判断, 这些家具是否可以由两辆车一次运送到目的地, 所有合法状态记录在一个数组state[]里.
对这些状态背包, dp[ i ][ j ] 表示使用前i个合法状态, 状态 j 需要的最少运送次数. 如果状态 j 和状态 state[i] 没有冲突(同一个家具只需要运送一次). 则

dp[ i ][ j | state[i] ] = min(dp[ i ][ j | state[i]] , dp[ i-1 ][ j ] + 1 )

最后答案就是dp[ .. ][ (1<

HDU 3466 Proud Merchants

http://acm.hdu.edu.cn/showproblem.php?pid=3466

【Description】

每个商品价格p, 至少有q元才能购买, 价值v. 求最大价值

n个物品, 1<=n<=500, 初始有m元, 1<=m<=5000. 1<=p<=q<=100, 1<=v<=1000

【Sample Input】

2 10 # 2个物品, 10元钱
10 15 10 # (p1, q1, v1)
5 10 5 # (p2, q2, v2)
3 10 # 3个物品, 10元钱
5 10 5 # p1, q1, v1
3 5 6 # p2, q2, v2
2 7 3 # p3, q3, v3

【Sample Output】

5 # 只能买第二个物品
11 # 先买第一个物品, 再买第二个物品

考虑2个商品A (p1, q1), B(p2, q2).假设单独购买A, 单独购买B, 都可以买下.
此时如果要购买A和B, 购买顺序对钱的需求不同.如果先买A再买B ,则需要有p1+q2的钱. 先买B再买A, 则需要有p2+q1的钱.
当然是对钱的需求越小, 越优. 如果先买A更优. 则p1+q2 < p2+q1. 即q1-p1 > q2-p2. 因此qi - pi越大的物品, 越先购买约好. 所以对 qi-pi 从小到大排序. 然后01背包即可.

HDU 4281 Judges' response

http://acm.hdu.edu.cn/showproblem.php?pid=4281

【Description】

每位选手坐标为（xi，yi），所需要占用的时间为vi，现在共有n个选手，每个裁判最多贡献m个单位的时间解决问题，
1）求最少需要派出多少教练；
2）若教练数量足够多，解决完所有问题并返回起点（第一个选手所在位置），求最短路径和。
（2<=n<=16，0<=m<=100000，0<=vi<=1000，0<=xi,yi<=1000）

【Sample Input】
3 3 # 3个选手 每个教练的时间为3
0 0 # 选手1坐标
0 3
0 1
0 # 选手1需要占用的时间
1
2

3 1
0 0
0 3
0 1
0
1
2

【Sample Output】
1 6 # 只需一个教练 最短距离为6
-1 -1 # 不能满足条件

1、普通01背包
2、TSP问题：旅行商问题，即TSP问题（Travelling Salesman Problem），又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

1）TSP问题：f[i][s]=min(f[i][s], f[j][s’]+dis[j][i]);  //当前在i 状态为s经过的最小距离
           g[s]=min(g[s], f[i][s]+dis[i][0]);  //当前状态为s 再返回原点的最小距离
2）MTSP问题：g[s]=min(g[s], g[a|1]+g[b|1]);

完全背包

模型：01背包的基础上，每件物品可以选择无限件

方程：

　　f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]); // 0 <= k <= j/v[i]

优化：

    for(int i=1; i<=n; i++)
        for(int j=v[i]; j<=m; j++)  //从小到大转移
        　f[j]=max(f[j], f[j-v[i]]+w[i]);

多重背包

模型：01背包的基础上，每件物品可以选择c[i]件

方程：

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

优化：

1、二进制拆分
    对于每一种物品，拆分为1, 2, 4, .. , 2^k, c[i]-2^k个，体积与价值乘上对应系数，做01背包。
2、单调队列优化
    f[j]=min(f[j-k*v[i]]+k*w[i]); //0<=k<=min(c[i], j/v[i])
    令j=a*v[i]+b, 则f[j]=min(f[a*v[i]+b-k*v[i]]+k*w[i]);
    在等式两边同时减去a*w[i], 则f[j]-a*w[i]=min(f[b+(a-k)*v[i]]-a*w[i]+k*w[i]);
    令t=a-k, 则f[j]=min(f[b+t*v[i]]-t*w[i])+a*w[i];
    此时f[j]的转移满足单调队列优化条件，程序得到优化

POJ 1742 Coins

http://poj.org/problem?id=1742

【Description】

n种硬币，面值分别为v[i]，数量分别为c[i]，若分别购买价格为1，2，3，…，m－1，m的商品，有几种情况能成功购买。
（1<=n<=100，1<=m<=100000，1<=vi<=100000，0<=ci<=1000）

【Sample Input】

3 10 #n种硬币，商品价格为1，2，3，…，9，10
1 2 4 2 1 1 #硬币面值分别为1，2，4，数量分别为2，1，1
2 5
1 4 2 1
0 0

【Sample Output】

8 #能成功购买的为：1，2，3，4，5，6，7，8
4

1）单调队列优化

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=100+10, maxm=100000+10;
int n, m, v[maxn], c[maxn], f[maxm];
int fir, tail, q[maxm], p[maxm];
void Zero(int i)
{
    for(int j=m; j>=v[i]; j--)  f[j]=max(f[j], f[j-v[i]]+v[i]);
    return ;
}
void Com(int i)
{
    for(int j=v[i]; j<=m; j++)  f[j]=max(f[j], f[j-v[i]]+v[i]);
    return ;
}
void Multi(int i)
{
    for(int j=0; j<v[i]; j++)
    {
        fir=tail=1;
        for(int k=j, h=0; k<=m; k+=v[i], h++)
        {
            while(fir!=tail&&k-p[fir]>v[i]*c[i])    ++fir;
            int tmp=f[k]-h*v[i];
            while(fir!=tail&&q[tail-1]<tmp)   --tail;
            q[tail++]=tmp, p[tail]=k;
            f[k]=q[fir]+h*v[i];
        }
    }
    return ;
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        memset(f, 0, sizeof f);
        for(int i=1; i<=n; i++) scanf("%d", &v[i]);
        for(int i=1; i<=n; i++) scanf("%d", &c[i]);
        for(int i=1; i<=n; i++)
        {
            if(c[i]==1) Zero(i);
            else if(c[i]*v[i]>=m) Com(i);
            else Multi(i);
        }
        int ans=0;
        for(int i=1; i<=m; i++) ans+=(f[i]==i);
        cout<<ans<<endl;
    }
    return 0;
}

2）完全背包思想

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100+10, maxm=100000+10;
int n, m, a[maxn], c[maxn], g[maxm];
bool f[maxm];
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF&&n+m)
    {
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=n; i++) scanf("%d", &c[i]);
        int ans=0;
        memset(f, 0, sizeof f);
        f[0]=true;
        for(int i=1; i<=n; i++)
        {
            memset(g, 0, sizeof g);
            for(int j=a[i]; j<=m; j++)
                if((!f[j])&&(f[j-a[i]])&&g[j-a[i]]<c[i])
                {
                    f[j]=true;
                    g[j]=g[j-a[i]]+1;
                    ++ans;
                }
        }
        cout<<ans<<endl;
    }
    return 0;
}

混合背包

POJ 3260 The Fewest Coins

http://poj.org/problem?id=3260

【Description】

n种硬币，面值分别为v[i]，数量分别为c[i]，各种面值的硬币商店都拥有无限多，现在买价格为m的商品，求交易中所需流通硬币的最小数目。
（1<=n<=100，1<=m<=10000，1<=vi<=120，0<=ci<=10000）

【Sample Input】

3 70 # 3种硬币 商品价格70
5 25 50 # 硬币面值分别为5 25 50
5 2 1 # 5*5，25*2，50*1

【Sample Output】

3 # 给商家25+50，补回5，所流通的硬币数目为3

将商店找补的硬币数目视为负数做完全背包，购买者拥有的硬币做多重背包

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100+10, maxm=20000+10, p=20000, INF=0x7f7f7f7f;
int n, m, v[maxn], v1[maxn], c[maxn], f[maxm];
int N, v2[maxm], w[maxm];
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &v[i]);
            v1[i]=-v[i];
        }
        for(int i=1; i<=n; i++) scanf("%d", &c[i]);
        N=0;
        for(int i=1; i<=n; i++)
            for(int sum=0, tmp=1; sum<=c[i]; tmp<<=1)
                if(sum+tmp<c[i]) v2[++N]=tmp*v[i], w[N]=tmp, sum+=tmp;
                else
                {
                    v2[++N]=(c[i]-sum)*v[i], w[N]=(c[i]-sum);
                    break;
                }
        memset(f, 0x7f, sizeof f);
        f[0]=0;
        for(int i=1; i<=N; i++)
            for(int j=p; j>=v2[i]; j--)
                if(f[j-v2[i]]!=INF) f[j]=min(f[j], f[j-v2[i]]+w[i]);
        for(int i=1; i<=n; i++)
            for(int j=p+v1[i]; j>=0; j--)
                if(f[j-v1[i]]!=INF) f[j]=min(f[j], f[j-v1[i]]+1);
        if(f[m]!=INF) cout<<f[m]<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

分组背包

分组背包就是有很多物品分属不同的物品组，每个物品组中只能选一个。
分组背包的公式：

F[k,v]=max(F[k−1,v],F[k−1,v−Ci]+Wi  [ item i∈group k ])

伪代码

for k ← 1 to K
  for v ← V to 0            # 这重循环一定要在 foreach item的外面..
    for all item i in group k
      F [v] ← max{F [v], F [v − Ci ] + Wi }

依赖背包

依赖背包

​ 这是《背包九讲》中的一讲，是从一道非树形的依赖背包讲起的，是说一些物品依赖于一个物品，但这些依赖的物品下面没有了依赖的物品。那么我们就可以将其化为分组背包去做。

​ 依赖背包的思想就是把主件的空间空出来，对附件做0-1背包，然后就能得到一系列的得到费用依次为0…V−Ck所有这些值时相应的最大价值Fk[0…V−Ck]Fk[0…V−Ck](其中Ck是主件的费用),那么我们就将附件与主件变成了V-Ck+1个物品的物品组.显然这些费用都是互斥的，你只能选择一个费用对吧。这是很好理解的，这个物品组其实就变成了一个泛化物品。

​ 对于主件与附件化为的这个物品组，我们得到费用为v的物品的价值就是 F[v−Ck]+WkF[v−Ck]+Wk 。对于众多的主件与附件化为的物品组，我们套分组背包的公式做就可以了。

更一般的问TWQ

​ 这时我们就不能将一个主件下面的附件单一的做0-1背包了，因为附件下面还有附件。例如主件下有附件1，附件2，然后附件1下面有个附件组a，附件2下面有个附件组b，那我们就可以将附件组a做0-1背包搞一 个AS 物品组，附件组b做0-1背包搞一个物品组，那么我们的主件下面就有了两个物品组。

​ 这时候我们需要做的便是对两个物品组做分组背包，这时候这个主件就被搞成了一个物品组。众多主件搞成了众多的物品组。最后在进行分组背包。最底层是0-1背包，往上走就变成了分组背包。这个过程可以通过dfs实现,复杂度 O(n∗c2)O(n∗c2)。

泛化背包

​ 在背包容量为 V 的背包问题中,泛化物品是一个定义域为 0 . . . V中的整数的函数 h,当分配给它的费用为 v 时,能得到的价值就是 h(v)。这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组 h[0 . . . V ],给它费用 v ,可得到价值 h[v]。

​ 把两个泛化物品合并成一个泛化物品的运算,就是枚举体积分配给两个泛化物
品,满足: G[j]=max(G1[j−k]+G2[k])(C>=j>=k>=0). 把两个泛化物品合并的时间复杂度是 O(C^2) 。

​ 把每个物品为根的子树视为一个泛化物品. 每个子树的泛化物品求解就相当于合并这个子树的根的叶子节点的每个泛化物品.

​ 泛化物品的并:因为两个泛化物品之间存在交集,所以不能同时两者都取,那么我们就需要求泛化物品的并,对同一体积,我们需要选取两者中价值较大的一者,效率 O(C)。G[j]=max(G1[j],G2[j])(C>=j>=0)

NOIP2006 金明的预算方案

https://www.rqnoj.cn/problem/6

【Description】

　　金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
​ 主件 附件
​ 电脑 打印机，扫描仪
​ 书柜 图书
​ 书桌 台灯，文具
​ 工作椅 无
　　如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
　　设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]w[jk]。（其中为乘号）请你帮助金明设计一个满足要求的购物单。

【Sample Input】

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

【Sample Output】

2200

NCPC2014 Outing

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1580

【Description】

有一辆能载客m的车，有n个人，然后第i个人上车的条件是第a[i]个人要上车，问最多能上几个

【Sample Input】

4 4
1 2 3 4

【Sample Output】

4

泛化物品的并:

因为两个泛化物品之间存在交集,所以不能同时两者都取,那么我们就需要求泛化物品的并,对同一体积,我们需要选取两者中价值较大的一者,效率 O(C)。

G[j] = max{ G1[j] , G2[j] } (C>=j>=0)

重新考虑对以 i 为根的子树的处理,假设当前需要处理 i 的一个儿子 s。

如果我们在当前的 Fi 中强制放入物品 s 后作为以 s 为根的子树的初始状态的话,那么处理完以 s 为根的子树以后,Fs 就是与 Fi 有交集的泛化物品(实际上是 Fs 包含 Fi),同时,Fs 必须满足放了物品 s,即 Fs[j] (Vs>j>=0)已经无意义了,而 Fs[j](C>=j>=Vs)必然包含物品 s。为了方便,经过处理以后,在程序中规定只有 Fs[j](C-Vs>=j>=0)是合法的。

void calc(int u, int C){
    for(int x=head[u]; x!=-1; x=es[x].next){
        int v = es[x].v;
        for(int i=0; i<=C; i++)
            dp[v][i] = dp[u][i];
        calc(v, C-V[v]);
        for(int i=V[v]; i<=C; i++){
            dp[u][i] = std::max(dp[u][i], dp[v][i-V[v]] + W[v]);
            //到了最低层其实就是在做0-1背包
        }
    }
}

ENDS

delicious DP

have fun：）