给出洛谷P1485的代码
时间: 2024-02-17 17:53:00 浏览: 31
题目链接:https://www.luogu.com.cn/problem/P1485
下面是洛谷 P1485 的 AC 代码,使用的是 C++ 语言:
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, a[10005], f[10005][505];
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= a[i])
f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]);
}
int ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, f[n][i]);
printf("%d", ans);
return 0;
}
```
其中,`n` 表示物品的个数,`m` 表示背包的最大容量,`a` 数组表示每个物品的重量,`f` 数组表示状态转移数组。
该算法的时间复杂度为 $O(nm)$,可以通过此题。