1 条题解

  • 0
    @ 2026-10-2 2:21:44

    区分不限次数与有限次数,先将有限次数限制到容量可容纳的数量,再二进制拆分;使用 long long 保存总价值。

    #include <bits/stdc++.h>
    using namespace std;
    int main(){int cap,n;cin>>cap>>n;vector<long long>d(cap+1);while(n--){int w,count;long long value;cin>>w>>value>>count;if(count==0){for(int j=w;j<=cap;j++)d[j]=max(d[j],d[j-w]+value);}else{count=min(count,cap/w);for(int k=1;count;k*=2){int take=min(k,count);count-=take;int cost=take*w;for(int j=cap;j>=cost;j--)d[j]=max(d[j],d[j-cost]+take*value);}}}cout<<d[cap]<<"\n";}
    
    • 1

    信息

    ID
    3945
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者