您说的是滚动数组吗?
by hellomath @ 2018-10-17 11:56:10
@[larryzhong](/space/show?uid=20438)
```cpp
#include<iostream>
using namespace std;
int m,n,v[100000],w[100000],f[100000];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
int low=0,sum=0;
if(i!=1)sum+=w[i];
low=max(sum,w[i]);
for(int j=m;j>=low;j--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
cout<<f[m];
}
```
by lqhsr @ 2018-10-17 11:58:57
```cpp
int low=0,sum=0;
if(i!=1)sum+=w[i];
low=max(sum,w[i]);
for(int j=m;j>=low;j--){
```
这里
by lqhsr @ 2018-10-17 11:59:13
确实用了滚动一维数组
by lqhsr @ 2018-10-17 11:59:50
一维背包不是很好写吗???为什么要滚动数组。。。
by 览遍千秋 @ 2018-10-17 12:17:38
@[灰狼与蔷薇](/space/show?uid=28910) “大佬的世界您不懂” --ouuan.
by Rbu_nas @ 2018-10-17 12:26:30
@[灰狼与蔷薇](/space/show?uid=28910)
不是 我是说加常数优化更慢了
by lqhsr @ 2018-10-17 17:36:42