分组背包
2026-06-12 19:55:29
发布于：上海
35阅读
0回复
0点赞
万能开头@78鼠鼠 @156****6690@仰天长啸你爹驾到@AC酱
struct node{
int w,v;
};
vector<node>ve[114514];
for(int i=1;i<=t;i++){
for(int j=0;j<=c;j++){
dp[i][j]=dp[i-1][j];//不拿物品
for(int k=0;k<ve[i].size();k++){
if(j>=ve[i][k].w)dp[i][j]=max(dp[i][j],dp[i-1][j-ve[i][k].w]+ve[i][k].v);
}
}
}
溢位
struct node{
int w,v;
};
vector<node>ve[114514];
int main(){
int c,n,t;
cin>>c>>n>>t;
int dp[114514];
for(int i=0;i<n;i++){
int W,C,P;
cin>>W>>C>>P;
ve[P].push_back({W,C});
}
for(int i=1;i<=t;i++){
if(ve[i].size()==0)continue;
for(int j=c;j>=0;j--){
for(int k=0;k<ve[i].size();k++){
if(j>=ve[i][k].w)dp[j]=max(dp[j],dp[j-ve[i][k].w]+ve[i][k].v);
}
}
}cout<<dp[c];
}
有帮助，赞一个