题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=1010;
int main(){
int q[N],w[N],n,weight,s[N][N];
cin>>n>>weight;
for(int i=0;i<=n;i++){
s[0][i]=0;
s[i][0]=0;
}
for(int i=1;i<=n;i++){
cin>>q[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=weight;j++){
if(q[i]<=j){
s[i][j]=max(s[i-1][j],s[i-1][j-q[i]]+w[i]);
}else{
s[i][j]=s[i-1][j];
}
}
}
printf("%d",s[n][weight]);
}
背包问题,最简单的DP
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla