首页 > 其他分享 >动态规划--DP

动态规划--DP

时间:2023-10-05 21:00:26浏览次数:32  
标签:背包 -- max int 价值 物品 动态 DP

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

背包

01背包

每个物体只有两种可能的状态(取与不取),对应二进制中的 \(0\) 和 \(1\),这类问题便被称为「0-1 背包问题」。

状态转移方程:

\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) \]

这里如果直接采用二维数组,有多余空间浪费

由于每个物品只有选或不选两种情况,即最多选一次,故可从体积出发逆向枚举每个物品

\[for(int\ j=m;j>=v[i];j--) \]

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

时间复杂度:\(O(n\times v)\)

点击查看代码
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]);
}

完全背包

完全背包模型与 \(0-1\) 背包类似,与 \(0-1\) 背包的区别仅在于一个物品可以选取无限次,而非仅能选取一次。

虑一个朴素的做法:对于第 i 件物品,枚举其选了多少个来转移。这样做的时间复杂度是 \(O(n^3)\) 的。

状态转移方程如下:

\[f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) \]

考虑做一个简单的优化。可以发现,对于 \(f_{i,j}\),只要通过 \(f_{i,j-w_i}\) 转移就可以了。因此状态转移方程为:

\[f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) \]

时间复杂度:\(O(n\times v)\)

理由是当我们这样转

每个物品可选无数次,故可以从体积出发正向枚举每个合法的物品

\[for(int\ j=1;j<=m;j++) \]

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

点击查看代码
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]);
}

多重背包

多重背包也是 \(0-1\) 背包的一个变式。与 \(0-1\) 背包的区别在于每种物品有 \(k_i\) 个,而非一个。

一个很朴素的想法就是:把「每种物品选 \(k_i\) 次」等价转换为「有 \(k_i\) 个相同的物品,每个物品选一次」。这样就转换成了一个 \(0-1\) 背包模型,套用上文所述的方法就可已解决。状态转移方程如下:

\[f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) \]

时间复杂度 \(O(W\sum_{i=1}^nk_i)\)。

点击查看代码
for(int i = 1; i <= n; i ++)
{
    for(int j = 0; j <= m; j ++)
    {
        for(int k = 0; k <= s[i]&&k * v[i] <= j; k ++)
		    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
    }
}

混合背包

混合背包就是将前面三种的背包问题混合起来,有的只能取一次,有的能取无限次,有的只能取 \(k\) 次。

按照背包种类分类求解,求最优解

例. 混合背包问题

题目描述:

有 N 种物品和一个容量是 V 的背包。

物品一共有三类:

·第一类物 品只能用\(1\)次(\(01\)背包);
·第二类物品可以用无限次(完全背包);
·第三类物品最多只能用 \(s_i\) 次(多重背包);每种体积是 \(v_i\),价值是 \(w_i\)。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式:

第一行两个整数,\(N,V\),用空格隔开,分别表示物品种数和背包容积。

接下来有 \(N\) 行,每行三个整数 \(v_i,w_i,s_i\),用空格隔开,分别表示第 i 种物品的体积、价值和数量。

·\(s_i=−1\) 表示第 \(i\) 种物品只能用1次;
·\(s_i=0\) 表示第 \(i\) 种物品可以用无限次;
·\(s_i>0\) 表示第 \(i\) 种物品可以使用 \(s_i\)次;

输出格式:

输出一个整数,表示最大价值。

输入

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

输出

8

点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 1e3 + 10;

int v[N], w[N], s[N], f[N];
int n, m;

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        cin >> w[i] >> v[i] >> s[i];
        if(!s[i])
            for(int j = w[i]; j <= m; j ++)
                f[j] = max(f[j], f[j - w[i]] + v[i]);
        else
        {
            if(s[i] == -1) s[i] = 1;
            for(int k = 1; k <= s[i]; k *= 2)
            {
                for(int j = m; j >= k * w[i]; j --)
                    f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);
                s[i] -= k;
            }
                
            if(s[i])
                for(int j = m; j >= s[i] * w[i]; j --)
                f[j] = max(f[j], f[j - s[i] * w[i]] + s[i] * v[i]);
        }
    }
    cout << f[m] << endl;
}

signed main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

二进制优化

具体地说就是令 \(A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)\) 分别表示由 \(2^{j}\) 个单个物品「捆绑」而成的大物品。特殊地,若 \(k_i+1\) 不是 \(2\) 的整数次幂,则需要在最后添加一个由 \(k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}\) 个单个物品「捆绑」而成的大物品用于补足。

将每种物品按照上述方式拆分后,使用 0-1 背包的方法解决即可。

时间复杂度: \(O(W\sum_{i=1}^n\log_2k_i)\)

点击查看代码
for(int i = 1; i <= n; i ++)
	{
		cin >> w >> v >> s;
		int k = 1;
		while(s > k)
		{
			s -= k;
			p[cnt ++] = {w * k, v * k};
			k *= 2;
		}
		p[cnt ++] = {w * s, v * s};
	}
	for(int i = 0; i < cnt; i ++)
		for(int j = m; j >= p[i].w; j --)
			f[j] = max(f[j], f[j - p[i].w] + p[i].v);
			

单调队列优化

点击查看代码
for(int i = 1; i <= n; i ++)
    {
        for(int r = 0; r < v[i]; r ++)
        {
            int hh = 0, tt = -1;
            for(int j = r; j <= m; j += v[i])
            {
                while(hh <= tt&&j - q[hh] > v[i] * s[i]) hh ++;
                while(hh <= tt&&f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) tt --;
                q[++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

二维费用背包

和 \(0-1\) 背包问题类似,不同的是选一个物品会消耗两种价值(经费、时间),可对每种价值进行\(0-1\)背包

点击查看代码
for(int i = 0; i < n; i ++)
{
    for(int j = V; j >= v[i]; j --)
    {
        for(int l = W; l >= w[i]; l --)
            f[j][l] = max(f[j][l], f[j - v[i]][l - w[i]] + a[i]);
    }
}

分组背包

从「在所有物品中选择一件」变成了「从当前组中选择一件」,可对每一组进行一次 \(0-1\) 背包。

点击查看代码
for(int i = 1; i <= n; i ++)
{
    for(int j = m; j >= 0; j --)
    {
        for(int  k = 1; k <= s[i]; k ++)
            if(j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    }
}

有依赖的背包

考虑分类讨论。对于一个主件和它的若干附件,有以下几种可能:只买主件,买主件 + 某些附件。因为这几种可能性只能选一种,所以可以将这看成分组背包。

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

有依赖的背包问题

题目描述:

有 \(N\) 个物品和一个容量是 \(V\) 的背包。

物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。

如下图所示:

如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。

每件物品的编号是 \(i\),体积是 \(v_i\),价值是 \(w_i\),依赖的父节点编号是 \(p_i\)。物品的下标范围是 \(1…N\)。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式:

第一行有两个整数 \(N,V\),用空格隔开,分别表示物品个数和背包容量。

接下来有 \(N\) 行数据,每行数据表示一个物品。第 \(i\) 行有三个整数 \(v_i,w_i,p_i\),用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 \(p_i=−1\),表示根节点。 数据保证所有物品构成一棵树。

输出格式:

输出一个整数,表示最大价值。

输入

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出

11

点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 110;
vector<int> g[N];
int f[N][N];
int v[N], w[N];
int n, m, root;

void dfs(int x)
{
    for(int i = v[x]; i <= m; i ++)
        f[x][i] = w[x];
    for(int i = 0; i < g[x].size(); i ++)
    {
        int y = g[x][i];
        dfs(y);
        for(int j = m; j >= v[x]; j --)
        {
            for(int k = 0; k <= j - v[x]; k ++)
                f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int fa;
        cin >> v[i] >> w[i] >> fa;
        if(fa == -1) root = i;
        else
            g[fa].push_back(i);
    }
    dfs(root);
    cout << f[root][m] << "\n";
}
signed main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

泛化物品的背包

这种背包,没有固定的费用和价值,它的价值是随着分配给它的费用而定。在背包容量为 \(V\) 的背包问题中,当分配给它的费用为 \(v_i\) 时,能得到的价值就是 \(h\left(v_i\right)\)。这时,将固定的价值换成函数的引用即可。

杂项

根据贪心原理,当费用相同时,只需保留价值最高的;当价值一定时,只需保留费用最低的;当有两件物品 \(i,j\) 且 \(i\) 的价值大于 \(j\) 的价值并且 \(i\) 的费用小于 \(j\) 的费用时,只需保留 \(i\)。

背包问题变种

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用 \(g_{i,v}\) 表示第 \(i\) 件物品占用空间为 \(v\) 的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略(选或不选)。

求方案数

对于给定的一个背包容量、物品费用、其他关系等的问题,求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可。

例如 \(0-1\) 背包问题的转移方程就变成了:

\[\mathit{dp}_i=\sum(\mathit{dp}_i,\mathit{dp}_{i-c_i}) \]

初始条件:\(\mathit{dp}_0=1\)

因为当容量为 \(0\) 时也有一个方案,即什么都不装。

标签:背包,--,max,int,价值,物品,动态,DP
From: https://www.cnblogs.com/chfychin/p/17743474.html

相关文章

  • RF Micro Devices收购Sirenza Microdevices Inc.
    RFMicroDevices (RFMD),agloballeaderinthedesignandmanufactureofhighperformanceradiofrequencysystemsandsolutions,announcedthecompletionofitsacquisitionof SirenzaMicrodevicesInc.,asupplierofradiofrequencycomponents.Underthe......
  • P8565 Sultan Rage 题解
    P8565发现数列\(a\)增长的特别快,项数最多时是\(a_1=a_2=\cdots=a_{100}\),但这样也只会有一百多项就可以超过\(10^{18}\)。可以考虑搜索,因为搜索树会比较稀疏,函数dfs(val,cur)表示凑出\(x\)还需要\(val\),现在在考虑\(cur\)。但光是搜索肯定不能过这道题,考虑优......
  • P4133 [BJOI2012]最多的方案 题解
    P4133双倍经验发现斐波那契数列增长极快,不到\(100\)项就超过了\(10^{18}\),搜索树也极为稀疏,可以考虑搜索。爆搜肯定会超时,考虑优化:可行性剪枝。记忆化,去除重复的计算。改变搜索的顺序,因为先考虑小元素的话,会有较多的无用的搜索,且小元素较灵活,更容易凑到\(x\),故可......
  • gin上使用Grpc入门
    要在Go中使用基于Gin的gRPC,你需要执行以下步骤:安装gRPC:使用以下命令安装gRPC:goget-ugoogle.golang.org/grpcshell复制代码安装protoc-gen-go:使用以下命令安装protoc-gen-go插件,它用于将protocolbuffer文件生成Go代码:goget-ugithub.com/golang/protobuf/protoc......
  • 38-5
    编写带头结点的算法,就地逆置小心断链#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}LNode,*LinkList;voidTailCreate(LinkList&L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;LNode......
  • 2023-2024-1 20231415吴昕洋 《计算机基础与程序设计》第一周学习总结
    这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求是什么2023-2024-1-计算机基础与程序设计第一周作业这个作业的目标简单浏览《计算机概论》,提出疑问,并尝试解决问题作业正文https://i.cnblogs.com/posts/edit教材内容·学习总结  ......
  • 第8章 排序
    一、插入排序基本思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列,直到全部记录插入完成直接插入排序时间复杂度:最好O(n):表中元素有序,最坏O(n2):表中元素逆序空间复杂度:O(1)稳定性:稳定,总是插入到相同元素的后面适用性:顺序、链式(从前往后查找指定元素......
  • 《软件工程:方法与实践》读书笔记1
    精益的思想本来就是源于汽车制造业,这本书就直接用日本丰田的实例很形象的告诉了我们什么是精益的思想。精益思想的核心是“消除浪费”,但是这个“浪费”和普遍被认可的观点有一些区别比如:仓库里还有原材料的剩余,普遍思想是全力生产产品以降低每个产品的平均的设备成本;然而,对于精......
  • 04_猫狗队列
    猫狗队列【题目】宠物、狗和猫的类如下:publicclassPet{ privateStringtype;publicPet(Stringtype){this.type=type;}publicStringgetPetType(){returnthis.type;}}publicclassDogextendsPet{publ......
  • 38-4
    编写在带头结点的单链表L中删除最小值结点的高效算法,最小值结点唯一先在while中找到最小值结点,再释放空间#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}LNode,*LinkList;voidTailCreate(LinkList&L){L=(Lin......