P1616 疯狂的采药

发布时间 2023-08-23 23:29:52作者: 失控D大白兔

有n种药草,每种药草数量无限,给出采摘药草的时间和价值
同时给出总时间t,求能采摘的最大价值

1. 动态规划

void maxval(int v,vector<int>&c,vector<int>&w){ 
    int n = w.size();
    long long dp[v+1];
    memset(dp,0,sizeof(dp));
    long long res = 0;
    for(int i=0;i<n;i++)
        for(int j=c[i];j<=v;j++){
            dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
            res = max(res,dp[j]);
        }
    cout<<res;
    return;
}