背包问题
01背包问题
1
| max(f[i-1][j],f[i-1][j-v[i]]+w[i])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=1010;
int N,V;
int v[n],w[n];
int f[n][n];
int main()
{
cin>>N>>V;
for(int i=1;i<=N;i++)cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
{
for(int j=0;j<=V;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
int res=0;
for(int i=0;i<=V;i++)res=max(res,f[N][i]);
cout<<res<<endl;
return 0;
}
|
报错： [[Error] array bound is not an integer constant before ‘]’ token](https://alanhere.com/2021/01/11/array-size-constant/)
报错地方：全局变量 int n=1010;未加const
报错原因：一般而言，C/C++ 的编译器在编译时，一个数组的长度往往要求是静态已知的。因此，如果数组 array[n] 长度是借助一个变量 n 来确定，那么可以加上 const 限定符。const 关键字是 用于限定一个变量为只读。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=1010;
int N,V;
int v[n],w[n];
int f[n];
int main()
{
cin>>N>>V;
for(int i=1;i<=N;i++)cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
{
for(int j=V;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[V]<<endl;
return 0;
}
|
完全背包问题
1
| max(f[i-1][j],f[i][j-v[i]]+w[i])
|
