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

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