社区讨论

背包 DP 记录选中物品有什么更好的方法

RRyanhao
学术版参与者 5已保存回复 21

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mii9v8z1
此快照首次捕获于
2025/11/28 10:57
3 个月前
此快照最后确认于
2025/11/29 14:02
3 个月前
查看原帖
rt，我有一个方法，就是在 DP 的时候使用一堆 bitset 记录选中物品个数。
如下：
CPP
// P1048
#include <bits/stdc++.h>
using namespace std;

int t,m,w[105],v[105],f[1005];
bitset<105> g[1005];

int main() {
	cin >> t >> m;
	for (int i = 1; i <= m; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = t; j >= w[i]; j--) {
            if (f[j] < f[j-w[i]]+v[i]) {
                f[j] = f[j-w[i]]+v[i];
                g[j] = g[j-w[i]]; g[j][i] = 1;
            }
		}
	}
	cout << f[t] << " " << g[t];
	return 0;
}
时间复杂度大概 O(m2wt)O\left(\dfrac{m^2}wt\right)。

回复

共 21 条回复，欢迎继续交流。

正在加载回复...