题目分析
代码如下
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
for (int k = 0; k * v[i] <= j; k ++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
printf("%d\n", f[n][m]);
return 0;
}
二维优化
欸!我们会 $\huge\color{orange}{\textit{惊奇}}$ 的发现 $\huge\color{red}{TLE}$ 。本来的话最大时间复杂度是 $10^9$,概率能过,现在卡了一个数据,就 $ji$ 了。
二维优化代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
}
printf("%d\n", f[n][m]);
return 0;
}
一维优化
$\huge\color{orange}{\textit{来都来了}}$,看这情形,不优化成个 $一维$ 状态有点说不过去.
一维优化代码如下
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
printf("%d\n", f[m]);
return 0;
}
终极代码
嘛,还能再压缩一下下,泥看那个 $\huge\color{purple}{\textit{w, v}}$ 这两个数组不顺眼,你肯定看不顺眼!!!别急,让我们来处理掉他们。
首先,它们都是在更新状态的时候用到的自己那一层的数据,那么我们完全可以在更新状态之前即时读进来嘛。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
scanf("%d%d", &n, &m);
while (n --)
{
int v, w;
scanf("%d%d", &v, &w);
for (int j = v; j <= m; j ++)
f[j] = max(f[j], f[j - v] + w);
}
printf("%d\n", f[m]);
return 0;
}