qwq
by fxygr2333_IAKIOI @ 2023-02-22 18:26:30
$O(nm)$ 数组会炸
完全背包正解两重循环，时间会炸
by Mathew_Miao @ 2023-02-22 18:35:14
空间用滚动数组
```cpp
#include <iostream>
#define ll long long
#define maxn 10005
using namespace std;
int w[maxn],c[maxn];
int f[maxn];
int main(){
int n,m;
cin >> m >> n;
for (int i=1;i<=n;i++) cin >> w[i] >> c[i];
for (int i=1;i<=n;i++){
for (int j=c[i];j<=m;j++){
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
cout << f[m];
}
```
by Mathew_Miao @ 2023-02-22 18:37:13
@[icaijy](/user/378195) 可以这样简化改进^-^
```cpp
#include<bits/stdc++.h>
using namesapce std;
int main()
{
long long dp[1001];
cin>>t>>m;
for(int i=1;i<=m;i++)
{
cin>>w[i]>>v[i];
}
//枚举可选择物品(i)
for(int i=1;i<=m;i++)
{
//枚举背包容量(j)
for(int j=t;j>=0;j--)
{
if(w[i]<=j)
{ //不选择,选择 做对比
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
else
{
dp[j]=dp[j];
}
}
}
cout<<dp[t];
return 0;
}
```
//12岁小孩，别介意……
by Danna2012 @ 2024-03-07 20:53:50