01 背包 bf
2026-05-30 21:04:21
发布于：上海
62阅读
0回复
0点赞
依旧骚扰挂同学@78鼠鼠 @156****6690@仰天长啸你爹驾到@AC酱
for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++){
if(j<w[i])dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
时间复杂度
空间复杂度
P1048 一眼模版（
namespace HQ{
#define int long long
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void Main(){
init();
int c,n,w[1145],v[1145],dp[1145][1145];
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++){
if(j<w[i])dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}cout<<dp[n][c];
return ;
}
}
P1060 加个乘法过（
namespace HQ{
#define int long long
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void Main(){
init();
int c,n,w[1145],v[1145],dp[41][114514];
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
v[i]*=w[i];
}for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++){
if(j<w[i])dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]*v[i]);
}
}cout<<dp[n][c];
return ;
}
}
一维数组 dp
for(int i=1;i<=n;i++){
for(int j=c;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
}
}
有帮助，赞一个