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

http://uva.onlinejudge.org/index.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题目一样的思想:

http://blog.csdn.net/u013480600/article/details/40376143

一般我们做的背包问题都是问你<=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