http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2340
题目大意:(如题)
输入输出:(如题)
解题思路:
1.01背包问题(不同的是可以放同种类的物体)
2.建立dp数组,dp[i]表示容量为i时最大的分数,动态规划公式如下:
dp[j]=dp[j](j<cost[i])
dp[j]=max(dp[j],dp[j-cost[i]+score[i]])(cost[i]<=j<=m)
3.最后dp[m]即为所求
核心代码:

for(i=1;i<=n;i++)
    {
        cin>>score>>cost;
        for(j=cost;j<=m;j++)
			if(dp[j]<dp[j-cost]+score)
				dp[j]=dp[j-cost]+score;
    }

发表评论

电子邮件地址不会被公开。

Post Navigation