《算法学习专栏》—— 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;
}

本栏目推荐文章
• 2024/1/13 算法笔记
• 解决 DELPHI 中执行外部命令出现屏幕一闪的问题的方法
• 从C++CLI工程的依赖库引用问题看.Net加载程序集机制
• Maven常见问题与原理技巧
• cleaning of llm corpus 大模型语料清洗
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• Eloquent 模型使用详解 Has One Through 远程一对一
• 算法学习Day26组合总和、分割回文串

算法 背包 模型 专栏 问题算法 背包 模型 专栏 算法 模型 状态 专栏 算法 背包 问题 线性 算法 专栏 问题 算法 背包 动态 问题 背包 算法 分数 问题 算法 背包 模型 笔记 背包 模型 基础 问题 listenablefuture专栏future问题 算法 垃圾 策略 专栏