这道题目跟 01 背包很像,只不过实在 01 背包的基础上加上了一个重量限制。
01 背包的动态转移方程是
$f_{i,\ j}\ =\ max\ (f_{i\ -\ 1, \ j},\ f_{i\ -\ 1,\ j\ -\ v_i}\ +\ w_i)$
那么这个多了个重量,那么可以再开一维,变成三维
$f_{i,\ j,\ k} \ = \ max \ (f_{i\ -\ 1,\ j,\ k}, \ f_{i\ -\ 1,\ j\ -\ v_i,\ k\ -\ m_i}\ +\ w_i)$
同 01 背包,它也可以压缩亿下空间,于是变成了
$f_{j,\ k} \ =\ max\ (f_{j\ -\ v_i,k\ -\ m_i}, f_{j,\ k})$
动态转移方程出来了,那么写代码也就轻松了。
#include <bits/stdc++.h>
using namespace std;
int n, V, M;
const int N = 1e3 + 5;
int v[N], m[N], w[N], f[N][N];
signed main () {
cin >> n >> V >> M;
for (int i = 1; i <= n; i ++) {
cin >> v[i] >> m[i] >> w[i];//体积,重量,价值
}
for (int i = 1; i <= n; i ++)
for (int j = V; j >= v[i]; j --)
for (int k = M; k >= m[i]; k --)
f[j][k] = max (f[j - v[i]][k - m[i]] + w[i], f[j][k]);//动态转移方程,01 背包的思路
cout << f[V][M];
}
学会举一反三,这道题目真的不难
哈哈终于有一次自己写的
等同与二维变成三维,然后不断向上递带
有没有头文件
%%%
这么一讲就肥肠清楚了
%%%tql
想问下,如何解出具体的物品有哪些?
参照一维 https://www.acwing.com/activity/content/problem/content/1282/
%%%
可以
谢谢 qaq
其实f数组没必要1e3大小,1e2那个限制就够了😀
顺手打了 1e3 emm
厉害