01背包-递推写法-建议序号不对齐

写法

之前习惯记忆递归写法，现在试一下直接递推：

序号不对齐，物品从1开始，f的第0行都是0. 这样好写一些

#include <cstdio>
#include <algorithm>
using namespace std;const int N = 1e3+5;
int v[N], w[N];
int n, vn;
int f[N][N];
int res = 0;int main() {scanf("%d %d", &n, &vn);for (int i = 1; i <= n; i++) {scanf("%d %d", &v[i], &w[i]);}// f[i][j], j体积下前i个物品的最大价值for (int i = 1; i <= n; i++) {for (int j = 0; j <= vn; j++) {if (j < v[i]) {f[i][j] = f[i-1][j];} else {f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);}}}res = f[n][vn]; // 背包容量范围是[0, vn]，所以要循环到vn，而关于物品是从1开始存的，范围是[1, n]printf("%d\n", res);
}

如果物品从0开始存，那么就要单独处理第一个物品：

#include <cstdio>
#include <algorithm>
using namespace std;const int N = 1e3+5;
int v[N], w[N];
int n, vn;
int f[N][N];
int res = 0;int main() {scanf("%d %d", &n, &vn);for (int i = 0; i < n; i++) {scanf("%d %d", &v[i], &w[i]);}// 数组从0开始，初始化0for (int j = 0; j <= vn; j++) {if (j < v[0]) {f[0][j] = 0;}else {f[0][j] = w[0];}}// i 第i个物品 j 剩余容量for (int i = 1; i < n; i++) {for (int j = 0; j <= vn; j++) {if (j < v[i]) {f[i][j] = f[i-1][j];} else {f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);}}}printf("%d\n", f[n-1][vn]);
}

暂时也放到hot100里吧，挺重要的题。