UVA 10465 Homer Simpson(全然背包: 二维目标条件)
option=com_onlinejudge&Itemid=8&page=show_problem&problem=1406
题意:
有两种汉堡包(汉堡数量无限多),第一种吃一个须要花n分钟,另外一种吃一个须要花m分钟. 如今你有t分钟的时间, 问你最少浪费几分钟不能吃汉堡(你每次要么完整的吃完一个汉堡,要么不吃). 当吃汉堡花费的时间达到最大时, 问你最多能吃几个汉堡?
分析:
本题的限制条件是: 总时间<=t分钟.
本题的目标条件是: 总时间尽量大, 假设时间同样的情况下汉堡数目越多越好.
二维(甚至多维)目标条件有两种方法能够做.
第一种方法是:先用全然背包求出最大时间tmax, 然后再用一次全然背包求出吃汉堡的时间正好等于最大时间tmax下, 最多能吃几个汉堡.
首先用全然背包求出最大时间tmax. 令dp[i][j]==x表示当决策完前i个汉堡后, 总时间不超过j分钟时最多能花x分钟. 那么有以下递推公式:
dp[i][j] = max( dp[i-1][j] , dp[i][j-time[i]]+time[i] )
前者表示一个i 汉堡都不选,后者表示至少选1个i汉堡.
dp全0. 终于tmax=dp[n][t].
然后我们求在花费时间正好tmax的情况下的最大汉堡数. 令dp[i][j]==x 表示决策全然i个物品后, 时间正好为j分钟时的最大汉堡数目为x个. 那么有以下递推公式:
dp[i][j] = max( dp[i-1][j] , dp[i][j-time[i]]+1)
前者表示一个i 汉堡都不选,后者表示至少选1个i汉堡.
dp全-1.且dp[0][0]=0.
终于最大汉堡数=dp[n][tmax].
另外一种方法是:
UVA12563题目一样的思想:
一般我们做的背包问题都是问你<=t的时间内, 怎样选择哪些汉堡(在不超过总时间的前提下)能使得吃的时间最长或 吃的汉堡最多. 可是本题须要同一时候考虑两个最优条件, 那么该怎么做呢?
我们令dp[i][j]==x 表示当决策全然前i个物品后(选或不选), 吃汉堡花的时间<=j时, 所得到的最优状态为x. (这里的x就不是平时我们所说的最长时间或最多歌曲数目了)
怎么理解最优状态为x这个事实呢? 如果有两种选择前i个汉堡的方法能使得决策完前i个物品且总时长<=j时的状态分别为x1 和x2.
那么假设x1状态的吃汉堡时间> x2状态的吃汉堡时间, 那么明显x1状态更优. 所以dp[i][j]应==x1.
假设x1状态的吃汉堡时间与x2的相等, 可是x2状态的吃汉堡数目 > x1状态的吃汉堡数目, 那么此时x2状态更优. 所以dp[i][j]应==x2.
经过上面的分析,我们能够用一个(具有吃汉堡时间和吃汉堡数目双属性的)结构体来表示一个状态. 且能够得到以下状态转移公式:
dp[i][j] = 最优(dp[i-1][j] , 在dp[i-1][j-time[i]]的基础上选择第i个汉堡后得到的新状态tmp )
全部dp初始化为0就可以. 终于我们所求为dp[n][t]
程序实现用的滚动数组,所以dp仅仅有[j]这一维.
AC代码1:用方法1两次DP做的
#include#include #include using namespace std;const int maxn=10000+5;int n,m,t;//相应题意的含义int time[5];//吃第i种汉堡所花时间int dp[maxn];int main(){ while(scanf("%d%d%d",&time[1],&time[2],&t)==3) { //递推最大时间 memset(dp,0,sizeof(dp)); for(int i=1;i<=2;i++) { for(int j=time[i];j<=t;j++) dp[j] = max(dp[j], dp[j-time[i]]+time[i]); } int tmax=dp[t]; //递推最大汉堡数目 memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=2;i++) { for(int j=time[i];j<=tmax;j++)if(dp[j-time[i]]!=-1) dp[j] = max(dp[j], dp[j-time[i]]+1); } //输出结果 printf("%d",dp[tmax]); if(t>tmax) printf(" %d",t-tmax); printf("\n"); } return 0;}
AC代码2:用方法2一次DP做的
#include#include #include using namespace std;const int maxn=10000+5;int n,m,t; //相应题意的含义int time[5];//吃第i种汉堡所花时间struct Node //每一个状态{ int time;//吃汉堡时间 int num; //吃汉堡数目 bool operator<(const Node &rhs)const { return time