动态规划解法：

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

思路：

对于天数 M 我们可以将它看做背包的最大容量，总成绩 W 即为背包可以装的总价值；对于对于单个物品来说，它的价值为

w i ​ ×c i

消耗的容量为它所花费的天数 x 。对于同一门科目的不同天数 0 到 m 天，我们可以把它看成一组，设该背包的容量为 j ，设该组某个物品占具 k 天的容量且具有价值

v=w i ​ ×c i

，然后从该组里面选出一个使得背包容量为

j-k

的最优成绩加上花费

k

天所获得成绩

v

最大，即为花费

j

天所获得的最优成绩。

AC代码：

CPP

#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;
}

题解：P11462 huaijiao 要加学

文章操作

动态规划解法：

思路：

AC代码：

相关推荐

评论

题解：P11462 huaijiao 要加学