这种转移方法是来自迷宫求最短路的记录方案的灵感,这个题里y
总只是提了一下,没有具体讲。
开一个PII g[i][j]
数组来记录,表示first
表示(i, j)
是由first这个点转移而来,second
表示由first
转移而来的时候第first
物品是否被选.
g[i][j] = {i + 1, false}
:表示(i,j)
这个状态是从没选第i + 1
个物品转移而来。
g[i][j] = {i + 1, true}
:表示(i,j)
这个状态是从选第i + 1
个物品转移而来。
然后边DP
边记录即可。
对于输出的过程:首先要判断一下g[i][j].second
是否为true
如果为true
,那么表示是由选择一个物品转移而来,那么当前体积需要跟着变化,那就是减去当前的v
,反之如果为false
,那么就不必减去当前的v
,还有注意这两种情况下i
都需要进行转移。
还要注意的就是求解的时候还是要倒序求,因为需要保证字典序最小,又因为这个WA
了一发。
int i = 1, j = m;
while (i <= n && j) {
if (g[i][j].second == true) {
int t = i;
cout << i << " ";
i = g[i][j].first;
j -= v[t];
} else {
i = g[i][j].first;
}
}
详细的代码有一些细节都在注释里了:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, bool> PII;
const int N = 1010;
int n, m;
int f[N][N];
int v[N], w[N];
PII g[N][N]; //first表示第几件物品 second表示选没选
vector<int> res;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i + 1][j];
g[i][j] = {i + 1, false};
if (j >= v[i]) {
if (f[i + 1][j - v[i]] + w[i] >= f[i][j]) { //注意这里一定要大于等于,因为为了保证字典序,能选必选
g[i][j] = {i + 1, true};
f[i][j] = f[i + 1][j - v[i]] + w[i];
}
}
}
}
int i = 1, j = m;
while (i <= n && j) { //这里一定是&& 一开始写成了||,调了半个多小时
if (g[i][j].second == true) {
int t = i; //这里一定要临时存一下i,因为下边i接着变成了它的上一个状态,而j要减去的是当前状态的v
cout << i << " ";
i = g[i][j].first;
j -= v[t];
} else {
i = g[i][j].first;
}
}
return 0;
}
开bool数组
其实不用这么复杂,g数组开一个bool数组就行
f[i + 1][j - v[i]] + w[i] >= f[i][j]
这里是保证最优解吧