题解：P11462 huaijiao 要加学

xdhking · 2025-01-01 00:09:03 · 题解

动态规划解法：

这里可以用分组背包来解决

思路：

对于天数 M 我们可以将它看做背包的最大容量， 总成绩 W 即为背包可以装的总价值；对于对于单个物品来说，它的价值为 w i ​ ×c i 消耗的容量为它所花费的天数 x 。对于同一门科目的不同天数 0 到 m 天，我们可以把它看成一组，设该背包的容量为 j ，设该组某个物品占具 k 天的容量且具有价值 v=w i ​ ×c i ，然后从该组里面选出一个使得背包容量为 j-k 的最优成绩加上花费 k 天所获得成绩 v 最大，即为花费 j 天所获得的最优成绩。

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct bag{
    double c,k;//c为学分，k为难度
}p[1005];
int main(){
    double n,dp[1005];
    int m;
    memset(dp,0,sizeof(dp));//背包初始清空
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>p[i].c;
    }
    for(int i=1;i<=n;i++){
        cin>>p[i].k;
    }
    for(int i=1;i<=n;i++){
//每次拿出第 i 门科目放入背包
        for(int j=m;j>=1;j--){
//从背包容量（消耗天数） m  开始放
            for(int k=j;k>=0;k--){
//物品的大小k（消耗天数）不可能超过背包的大小j，所以消耗的天数只能小于j
                double x=min(1.0,k/p[i].k)*100.0;
//从第 i 门科目j到0天这组中选出最优的成绩
                dp[j]=max(dp[j],dp[j-k]+x*p[i].c);
            }
        }
    }
    printf("%.4lf",dp[m]);
    return 0;
}