Acwing12(0/1背包+字典序)

题目链接：https://www.acwing.com/problem/content/12/

解题思路：

贴上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 5; 

int N, V; 
bool vis[maxn];
int f[maxn][maxn];
int v[maxn], w[maxn];

int main(void) {
//	freopen("in.txt", "r", stdin);
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i ++)
		scanf("%d%d", &v[i], &w[i]);
	
	for(int i = N; i >= 1; i --)
	for(int j = 1; j <= V; j ++) {
		int tmp1 = f[i + 1][j];
		f[i][j] = tmp1;
		if(j >= v[i]) {
			int tmp2 = f[i + 1][j - v[i]] + w[i];
			f[i][j] = max(f[i][j], tmp2);
		}
	}
	
	int tmp_v = V;
	int fi;
	for(int i = 1; i <= N; i ++) {
		if(f[i][tmp_v] <= f[i + 1][tmp_v - v[i]] + w[i] && tmp_v >= v[i]) {
			vis[i] = true;
			tmp_v -= v[i];
			fi = i;
		}
	}
	
	for(int i = 1; i <= N; i ++)
		if(vis[i]) {
			if(i == fi) printf("%d", i);
			else printf("%d ", i); 
		} 

	return 0;
}

总结：其实这道题目的原始版本的f[i, j]表示从1 - i物品且体积为j的组合的最大数值，但是稍微变化一下从后往前去dp，就能解决这道题目了。着实比较精妙。还需要继续练习dp。解题的过程感觉还是很快乐的。