@[李逸然123](/user/451850) 错误还是挺多的:
1. 01背包第二层循环是倒着的。
2. 转移应为 ```max(dp[i-1][j-v[i]]+w[i],dp[i][j]);```且转移前要给```dp[i]``` 初值,应写上```memcpy(dp[i], dp[i - 1], sizeof(dp[i - 1]));```。
是不是很麻烦,想要不这么麻烦的话,把```dp```数组第一维删掉即可。
by xixike @ 2021-11-05 19:08:10
初值就是把```dp[i-1]```全部赋值给```dp[i]```
by xixike @ 2021-11-05 19:08:43
可是这个转移方程在[另一个OJ](https://deeplearning.org.cn/problem/P1271)
上能A
我们信息学社团老师好像没讲一维数组的01背包
by 李逸然123 @ 2021-11-05 20:03:45
@[xixike](/user/158846)
by 李逸然123 @ 2021-11-05 20:06:26
@[李逸然123](/user/451850) 那那个 OJ 就是数据水了,显然转移的时候不能跟 ```dp[i-1][j]``` 判断。循环的话,正向循环是完全背包的写法。
by xixike @ 2021-11-05 20:11:03
一维的写法就是可以把物品那维删掉,因为没什么用,我可以给你个代码。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int w[110], v[110], f[1010];
int main(){
int m, n, t, i, j;
cin >> m >> n;
for (i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (i = 1; i <= n; i++)
for (j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m] << endl;
return 0;
}
```
by xixike @ 2021-11-05 20:13:22