首页 > 编程语言 >《算法学习专栏》—— DP问题之背包模型

《算法学习专栏》—— DP问题之背包模型

时间：2023-10-11 18:57:14浏览次数：40  
标签：背包 const int 模型 cin 专栏 题目 DP

2023年10月11日

更新于2023年10月11日

一、前言

本栏，为背包模型，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到背包的题目，也能加进来，不断完善。使用的分析方法均为闫式DP分析法。字臭。。。希望能用手写板慢慢写的好看。

二、背包模型

2.1 目前的模型

  1. 01背包模型
  2. 完全背包模型
  3. 多重背包模型
  4. 分组背包模型
  5. 多维费用背包模型

2.2 解决的问题

  1. 背包模型的最多不超过类型问题（\(f 全为 0\)且\(v >= 0\)）
  2. 背包模型的恰好类型问题（\(f[0] == 0\)且\(v >= 0\)）
  3. 背包模型的至少类型问题（\(f[0] == 0\)且\(v无限制，可以取小于零\)，方案和max(0, j - v)即可）
  4. 背包模型的方案数问题（不是最优）
  5. 背包模型的具体方案问题（分组背包）
  6. 多维背包模型的上述三类问题
    ...待更新、总结

2.3 降维优化

所有的背包模型都可以进行降维优化但要切记：

  • 完全背包模型，正向枚举
  • 其他背包，逆向枚举

三、题目实例

1. Acwing2 01背包问题

题目理解

代码实现


const int N = 1010;
int f[N][N];
int w[N], v[N];
int n, m;
int main()
{
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            
            if(j >= v[i])
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            else
                f[i][j] = f[i - 1][j];       
        }
    
    cout << f[n][m];
    
    return 0;
}

2. Acwing3 完全背包问题

题目理解

代码实现

const int N = 1010;
int f[N][N];
int n, m;
int w[N], v[N];

int main()
{
    cin >> n >>m;
    for(int i = 1; i <= n ;i++)
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j =1; j <= m; j++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= v[i])
                    f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
            }


    cout<<f[n][m];
    return 0;
}

3. Acwing4 多重背包问题

题目理解

代码实现

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


int main()
{
   cin >> n >>m;
   for(int i = 1; i <= n ;i++)
       cin >> v[i] >> w[i] >> s[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; 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]] + k * w[i]);

    cout<<f[n][m];
    return 0;
}

4. Acwing9 分组背包问题

题目理解

代码实现

const int N = 110;
int f[N][N], w[N][N], v[N][N];
int n, m, s[N];
int main()
{
    cin >> n >>m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];

    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            for(int k = 0; k <= s[i]; k++)
            {

                if(v[i][k] <= j)
                    f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]);
            }
        }


    cout<<f[n][m];
    return 0;
}

5. Acwing423 采药 01背包问题不超过类型

题目理解

代码实现

const int N = 1010;
int d[N][N], w[N], t[N];

void solve()
{
	int m, n;
	cin >> m >> n;

	for(int i = 1; i <= n; i++) cin >> t[i] >> w[i];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			d[i][j] = d[i - 1][j];
			if(j >= t[i])
				d[i][j] = max(d[i][j], d[i - 1][j - t[i]] + w[i]);
		}

	cout << d[n][m];

	return;
}

6. Acwing1024 装箱问题 01背包问题不超过类型

题目理解

代码实现

const int N = 40, M = 20000 + 10;
int w[N], d[N][M];

void solve()
{
	int n, v;
	cin >> v >> n;

	for(int i = 1; i <= n; i++) cin >> w[i];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= v; j++)
		{
			d[i][j] = d[i - 1][j];
			if(j >= w[i])
				d[i][j] = max(d[i - 1][j], d[i - 1][j - w[i]] + w[i]);
		}

	cout << v - d[n][v];
	return;
}

7. Acwing1022 多费用01背包问题不超过类型

题目理解

代码实现

const int M = 1010, N = 110, K = 510;
int f[M][K];
int v[N], w[N];


void solve()
{
	int n, m, k;
	cin >> m >> k >> n;

	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	for(int i = 1; i <= n; i++)
		for(int j = m; j >= v[i]; j--)
			for(int p = k; p >= w[i]; p--)
					f[j][p] = max(f[j][p], f[j - v[i]][p - w[i]] + 1);

	int res = f[m][k - 1];
	int blood = 0;
	for(int i = 0; i <= k; i++)
		if(f[m][i] == res)
		{
			blood = i;
			break;
		}

	cout << res << " " << k - blood;
	return;
}

8. Acwing278 数字组合 01背包问题恰好类型方案数问题

题目理解

代码实现

const int N = 110, M = 100010;
int f[M], a[N];
void solve()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];

	f[0] = 1;

	for(int i = 1; i <= n; i++)
		for(int j = m; j >= a[i]; j--)
			f[j] += f[j - a[i]];


	cout << f[m];
	return;
}

9. Acwing1023 买书 完全背包问题方案数不超过类型

题目理解

代码实现

const int N = 1010;
int a[5] = {0, 10, 20, 50, 100}, f[N];
void solve()
{

	int n;
	cin >> n;

	f[0] = 1;

	for(int i = 1; i <= 4; i++)
		for(int j = a[i]; j <= n; j++)
				f[j] += f[j - a[i]];

	cout << f[n];
	return;
}

10. Acwing1021 货币系统 完全背包问题方案数不超过类型

题目理解

代码实现

const int N = 20, M = 3010;
ll a[N], f[N][M], n, m;
void solve()
{

	cin >> n >> m;

	for(int i = 1; i <= n; i++) cin >> a[i];

	for(int i = 0; i <= n; i++) f[i][0] = 1;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			f[i][j] = f[i - 1][j];
			if(j >= a[i])
				f[i][j] += f[i][j - a[i]];
		}

	cout << f[n][m];
	return;
}

11. Acwing1019 庆功会 多重背包问题不超过类型

题目理解

代码实现

const int N = 510, M = 6010;

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

void solve()
{

	cin >> n >> m;

	for(int i = 1; i <= n; i++)
		cin >> v[i] >> w[i] >> s[i];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			f[i][j] = f[i - 1][j];

			for(int k = 0; k <= s[i]; k++)
				if(k * v[i] <= j)
					f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}


	cout << f[n][m];
	return;
}

12. Acwing1020 潜水员 多费用01背包问题至少类型

题目理解

代码实现

const int N = 30, M = 90, K = 1010;
int f[K][N][M], s[K], v[K], w[K];

void solve()
{
	memset(f, INF, sizeof f);

	int n, m, k;
	cin >> m >> k >> n;

	for(int i = 1; i <= n; i++)
		cin >> s[i] >> v[i] >> w[i];

	for(int i = 0; i <= n; i++) f[i][0][0] = 0;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			for(int p = 1; p <= k; p++)
			{
				f[i][j][p] = f[i - 1][j][p];
				f[i][j][p] = min(f[i][j][p], f[i - 1][max(0, j - s[i])][max(0, p - v[i])] + w[i]);
			}

			
	cout << f[n][m][k];

	return;
}

13. Acwing1013 机器分配 分组背包问题不超过类型、具体方案问题

题目理解

代码实现

const int N = 20, M = 20;
int w[N][N], f[N][M], p[N];
void solve()
{
	int n, m;
	cin >> n >> m;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> w[i][j];

	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= m; j++)
		{
			f[i][j] = f[i - 1][j];
			for(int k = 0; k <= j; k++)
					f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
		}

	cout << f[n][m] << endl;
	

	int j = m;

	for(int i = n; i; i--)
		for(int k = 0; k <= j; k++)
		{
			if(f[i][j] == f[i - 1][j - k] + w[i][k])
			{
				p[i] = k;
				j -= k;
				break;      // 不再往下找了
			}
		}


	for(int i = 1; i <= n; i++)
		cout << i << " " << p[i] << endl;

	return;
}

14. Acwing426 开心的金明 01背包问题不超过类型

题目理解

代码实现

const int N = 30000 + 10, M = 30;

ll d[N], p[M], v[M];
int n, m;
void solve()
{
	cin >> m >> n;

	for(int i = 1; i <= n; i++) cin >> v[i] >> p[i];

	for(int i = 1; i <= n; i++)
		for(int j = m; j >= v[i]; j--)
			d[j] = max(d[j], d[j - v[i]] + p[i] * v[i]);

	cout << d[m];

	return;
}

标签：背包,const,int,模型,cin,专栏,题目,DP
From： https://www.cnblogs.com/wxzcch/p/17757932.html

相关文章

  • C++ - UDP通信
    1.UDP通信流程UDP就比较简单了，步骤比tcp要少一些。连接过程图：  1.1服务器1.初始化套接字库WORDwVersion;WSADATAwsaData;interr;​wVersion=MAKEWORD(1,1);2.创建套接字SOCKETsockSrv=socket(AF_INET,SOCK_DGRAM,0);3.绑定//SOCKADDR_INaddrSrv......
  • DPDK-22.11.2 [四] Virtio_user as Exception Path
    因为dpdk是把网卡操作全部拿到用户层，与原生系统驱动不再兼容，所以被dpdk接管的网卡从系统层面（ipa/ifconfig）无法看到，同样数据也不再经过系统内核。如果想把数据再发送到系统，就要用到virtiouser。这种把数据从dpdk再发送到内核的步骤，就叫做exceptionpath。有关virtiouser，又有一......
  • WordPress网站被黑怎么办？【含解决方案】
    在我们的日常WordPress主题售后工作中，经常会有用户反馈网站出现问题，例如：阿里云提示后门木马文件；打开后跳转到其他地址；页面出现乱码；被添加了其他内容等，根据我们的经验，这种一般都是网站被黑导致的。 如何确认网站是否被黑根据以往经验，可以通过以下方式来判断：1、如果是阿里云提......
  • dotnet 8 WPF 支持在 RDP 远程桌面状态下启用渲染硬件加速
    本文将和大家介绍在dotnet8里WPF引入的新功能之一，在RDP远程桌面状态下启用渲染硬件加速在dotnet8之前，在用户进行RDP远程桌面时WPF应用将默认关闭硬件渲染加速以获得更好的兼容性。随着系统层的渲染架构的优化，比如在WDDM驱动模型里面，进行远程桌面的硬件加速已经是......
  • 《算法学习专栏》——DP问题之线性DP
    2023年10月10日更新于2023年10月10日一、前言本栏，为线性DP，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到线性DP的题目，也能加进来，不断完善。二、线性DP2.1目前的模型：数字三角形模型最长上升子序列模型2.2目前解决的问题：可以解决路径上的各种值。解决......
  • rsa dp泄露脚本
    已知c,e,n,dp求m（dp=d%(p-1)）importgmpy2fromCrypto.Util.numberimport*n=dp=c=e=tmp=e*dp-1#根据联立条件有:e*dp=1+k(p-1)，故求解p的式子为：(p-1)=(e*dp-1)/kforkinrange(1,e):#因为K上限只到e，故遍历求解iftmp%k==0:#验证(p-1)是否为整除结果......
  • Conveyor (CF E) (dp 差分/前缀 条件迷惑t)
     思路: 找各种性质1每一秒只有史莱姆进入起始点,然后他会选一个方向走(右或者下),每一秒史莱姆都会这样走在考虑前t秒内有S个史莱姆到达这个点,然后就会有s+1/2个往右走,s/2往下走而且问t秒只会有t-n-m-1秒后的时刻影响(诈骗t)于是利用dp+差......
  • QT-UDP网络编程
    QT_UDP网络编程用户数据报协议（UDP，UserDatagramProtocol);轻量的,不可靠,无连接,面向数据报的传输协议与TCP,特征:UDP通信在本质上不需要区分客户端和服务端,拥有socket的一方本身具有发送和接收数据报的能力.QUdpSocket继承于父类的QAbstractSocket,没有QTcpSocket的流功......
  • Java-网络编程（TCP-UDP）
    Java-网络编程（TCP-UDP）网络基础网络编程最主要的工作就是在发送端把信息通过规定好的协议进行组装包，在接收端按照规定好的协议把包进行解析，从而提取出对应的信息，达到通信的目的。中间最主要的就是数据包的组装，数据包的过滤，数据包的捕获，数据包的分析，当然最后再做一些处理，代码、开......
  • The 2nd Universal Cup. Stage 4: Taipei - I(状压DP)
    目录I.IntervalAdditionI.IntervalAddition题意给定一个长度为n$(1\len\le23)$的数组a。你可以进行一种操作：选择区间\([l,r]\)并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为0所需的最小操作次数？思路考虑差分数组无论怎么对于区间\([l,r......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99