#include <cstdio>
#include <iostream>
using namespace std;
const int N=1010;
int V[N],W[N];
int f[N][N];
int n,v;
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++) scanf("%d%d",&V[i],&W[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
f[i][j]=f[i-1][j];
if(j-V[i]>=0){
f[i][j]=max(f[i][j],f[i][j-V[i]]+W[i]);
}
}
}
cout<<f[n][v]<<endl;
return 0;
}
一维数组优化
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1010;
int V[N],W[N];
// int f[N][N];
int f[N];
int n,v;
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++) scanf("%d%d",&V[i],&W[i]);
for(int i=1;i<=n;i++){
for(int j=V[i];j<=v;j++){
f[j]=max(f[j],f[j-V[i]]+W[i]);
}
}
cout<<f[v]<<endl;
return 0;
}
题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla