UVA 10465 Homer Simpson(全然背包: 二维目标条件)

UVA 10465 Homer Simpson(全然背包: 二维目标条件)

UVA 10465 Homer Simpson(全然背包: 二维目标条件)

.php?

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<cstdio>
#include<cstring>
#include<algorithm>
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<cstdio>
#include<cstring>
#include<algorithm>
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<rhs.time || (time==rhs.time && num<rhs.num);}
}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++){Node tmp=dp[j-time[i]];tmp.time += time[i];tmp.num++;if(dp[j]<tmp) dp[j]=tmp;}}//输出结果printf("%d",dp[t].num);if(dp[t].time<t) printf(" %d",t-dp[t].time);printf("n");}return 0;
}