首页 > 代码库 > [二维费用背包DP]找啊找啊找GF
[二维费用背包DP]找啊找啊找GF
题目链接
思考
首先题目一定是背包DP（多读数据范围和题意）
其次一定是 二维费用的背包问题 （人品和金钱）
最后题目要求的是 在泡尽量多的妹子的情况下，花费最少的时间。
DP转移方程一定是二维的没错，但是要满足花费最少妹子最多的这个要求就比较难以解决了。不过也不要想这么多，先看看我的分析。
假设在求解过程中如果花X元RMP，Y单位RP可以到Z个MM，那么在泡第i个MM时，发现可以用X-rmb[i]元，Y-rp[i]单位RP泡到的MM数加上这个MM（也就是+1）比原来Z多，就替换它（因为你的原则是尽量多的泡MM）。
如果和Z一样多（即dp[j][k]==dp[j-RMB[i]][k-RP[i]]+1），这是就要考虑原来花的时间多呢，还是现在花的时间多。要是原来的多，就把时间替换成现在用的时间（因为你既然可以泡到相同数量的MM当然要省点时间去出题）。
所以应该用两个转移方程来实现DP，这里仔细思考思考怎么写吧。
#include <cstdio>#include <iostream>using namespace std;int RMB[105],TIME[105],RP[105],m,r,n,dp[105][105],F[105][105];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&RMB[i],&RP[i],&TIME[i]); scanf("%d%d",&m,&r); //优化实现 优化空间复杂度 for(int i=1;i<=n;i++) for(int j=m;j>=RMB[i];j--) for(int k=r;k>=RP[i];k--){ if(dp[j][k] < dp[j-RMB[i]][k-RP[i]]+1){ //如果能泡到的MM比之前多就替换 dp[j][k] = dp[j-RMB[i]][k-RP[i]]+1; F[j][k] = F[j-RMB[i]][k-RP[i]]+TIME[i]; } //泡的相同比较一下 时间 if(dp[j][k]==dp[j-RMB[i]][k-RP[i]]+1 && F[j][k] > F[j-RMB[i]][k-RP[i]]+TIME[i]){ F[j][k] = F[j-RMB[i]][k-RP[i]]+TIME[i]; } } printf("%d",F[m][r]); return 0; }
[二维费用背包DP]找啊找啊找GF
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。