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<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;
}