动态规划

发表于 更新于 分类于 阅读次数： Changyan：

动态规划

背包模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Dp{
    状态表示{
        集合{
            表示的是所有选法
                
            满足条件条件{
                1.只从前i个物品中选
                
                2.总体积<=j
            }
        }
            
        属性  Min,Max,数量
    }
    
    状态计算 集合划分
}

01背包问题

n个物品和一个容量为v的背包，每一个物品体积vi,价值wi,每件物品只能用一次.

求背包能装的下的情况下能装下的最大价值为多少,我们考虑有递推式：

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

再空间优化：

1
2
3
for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

完全背包问题

每件物品可以用无限次，只要装得下。

状态转移方程代码：

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

我们考虑对其做优化，参考01背包，先对空间做优化，然后我们可以推导出

对比上两个方程我们可以推导出：

实现代码：

1
2
3
for(int i=1;i<=n;i++)
    for(int j=v[i];j<=m;j++)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i])

多重背包问 题

每件物品的数量有限制，各为 Si：

1.朴素版

​ 核心思想：二进制优化；

​ 我们将s[i]拆分成二进制表示的1，2…2^k，其中2^k<=s[i]/2

​ 然后转化成01背包来做

​ 其中k=0,1,2…s[i]

我们将dp数组的行进行压缩可以得到：

实现代码:

1
2
3
4
for(int i=1;i<=n;i++)
    for(int j=m;j>=0;j--)
        for(int k=0;k<=s[i];k++)
            dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i])
2.二进制优化版

我们可以将每个物品的数量s做二进制优化，即将每一个s拆分成1,2,4….2^k,s+1-2^(k+1)。这样我们可以使用这些数表示任意1-s区间内的每一个数，并且时间复杂度也可以从原来的O(nms)优化到O(nmlogs)。然后我们呢对于拆分出来的物品用01背包的思路来做即可；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=1;i<=n;i++){  //二进制优化
        int a,b,c;
        cin >> a >> b >> c;
        int u=1;
        while(c>=u){
            v[++cnt]=a*u;
            w[cnt]=b*u;
            c-=u;
            u*=2;
        }
        if(c>0){
            v[++cnt]=a*c;
            w[cnt]=b*c;
        }
    }
    n=cnt;

分组背包问题

物品有n组，每一组有若干个，每一组最多选一个，求最大价值

因此本质上还是01背包问题，我们将其转化为01背包，只不过多一层循环k依次迭代更新每一组的各件物品；

1
2
3
4
for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<=s[i];k++)
                if(j>=v[i][k])dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);

关于题目的文字表述：