首页 > 其他 > 详细

一道令人抓狂的零一背包变式 -- UVA 12563 Jin Ge Jin Qu hao

时间:2019-02-12 23:34:21      阅读:32      评论:0      收藏:0      [点我收藏+]

标签:bre   std   一定的   isp   链接   struct   ostream   如果   动态规划   

题目链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4008

题目大意:

想象一下,你在KTV,想待久点,并且机器会让你唱完你歌再停。于是你选了劲歌金曲,678秒。现在你至少还剩一秒切到这首歌,而且每首歌必须唱完,现在问你你最久能待多久。

思路:

01背包,动态规划。但是01背包变式我第一次做的时候没有想到,结果误入歧途。。后面会贴代码,想直接看题解的不看便是,前面先说题解。

首先不断dp更新最大歌的数量,不算上劲歌金曲,然后用一个mx记录一下最大歌曲数量,注意,这里是为了限制你的决策。用时间作为背包容量进行dp,记录下最多歌曲数目,最后通过最多歌曲数目得出最多歌曲数目下的最长时间。至于为什么不能直接求,后面会给理由。

AC代码如下:

技术分享图片
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>

using namespace std;
const int jingejinqu = 678;
const int MX = 1e5+10;
int dp[MX];
int v[MX];

int main()
{
    int T;
    scanf("%d", &T);
    int k = 0;
    while(T--)
    {
        int summx = 0;
        memset(dp, -1, sizeof(dp));
        memset(v, 0, sizeof(v));
        int n, m;
        scanf("%d%d", &n, &m);
        dp[0] = 0; //这里注意一下,刚开始从0开始,不然无法进行下去
        for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
        for(int i = 1; i <= n; ++i)
            for(int j = m-1; j >= v[i]; --j)
            {
                if(dp[j-v[i]] >= 0) dp[j] = max(dp[j], dp[ j-v[i] ]+1);
                summx = max(summx, dp[j]);
            }
        for(int i = m-1; i >= 0; --i)
        {
            if(dp[i] == summx)
            {
                printf("Case %d: %d %d\n", ++k, summx+1, i+jingejinqu);
                break;
            }
        }

    }
}
View Code

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

下面是曲折的解题道路:

刚刚开始我直接当成了01背包裸题来解,思路也比较奇葩,就是直接解,定义了一个struct类来记录有没有选到:

技术分享图片
#include <iostream>
#include <cstdio>
#define ll long long
#include <algorithm>
#include <string.h>

using namespace std;
const int MX = 1e5+10;
const int jinggejinqu = 678;
ll dp[MX];
//ll val[MX];

struct {
    ll x;
    int flag;
} val[MX];

int main()
{
    int T;
    scanf("%d", &T);
    int k = 0;
    while(T--)
    {
        memset(dp, -1, sizeof(dp));
        memset(val, 0, sizeof(val));
        int cnt = 1;
        int n;
        ll m;
        scanf("%d%lld", &n, &m);
        for(int i = 1; i <= n; ++i) scanf("%lld", &val[i].x);
        for(int i = 1; i <= n; ++i)
        {
            ll x = dp[m];
            for(int j = m-1; j >= val[i].x; --j)
            {
                //dp[j] = max(dp[j], dp[ j-val[i] ]+val[i]);
                if(dp[j] < dp[ j-val[i].x ]+val[i].x)
                {
                    dp[j] = dp[ j-val[i].x ]+val[i].x;
                    //if(j == m) val[i].falg = 1;
                }
                else dp[j] = dp[j];
            }
            if(x+val[i].x == dp[m]) val[i].flag = 1;
        }

        for(int i = 1; i <= n; ++i) if(val[i].flag) cnt++;
        ll ans = dp[m]+jinggejinqu;
        printf("Case %d: %d %lld\n", ++k, cnt, ans);
    }
}
View Code

但是,WA了

后来继续想了个思路,2次dp:

技术分享图片
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>

using namespace std;
const int jingejinqu = 678;
const int MX = 1e7+10;
int dp1[MX], dp2[MX];
int v[MX];

int main()
{
    int T;
    scanf("%d", &T);
    int k = 0;
    while(T--)
    {
        int summx = 0;
        memset(dp1, -1, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        memset(v, 0, sizeof(v));
        int n, m;
        scanf("%d%d", &n, &m);
        dp1[0] = 0;
        for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
        for(int i = 1; i <= n; ++i)
            for(int j = m-1; j >= v[i]; --j)
            {
                if(dp1[j-v[i]] >= 0) dp1[j] = max(dp1[j], dp1[ j-v[i] ]+1);
                summx = max(summx, dp1[j]);
            }
        for(int i = 1; i <= n; ++i)
            for(int j = m-1; j >= v[i]; --j)
            {
                dp2[j] = max(dp2[j], dp2[ j-v[i] ]+v[i]);
            }
        printf("Case %d: %d %d\n", ++k, summx+1, dp2[m-1]+jingejinqu);

    }
}
View Code

还是WA了。。。

怎么也想不出哪里错了,于是百度,一看才知道:

下面取自博客:https://www.cnblogs.com/shi2015/p/4661971.html

由于要求是连续唱歌,且要求在最多歌曲数的情况下时间最长,如果按普通的背包存储,很难得到最长时间,因为f[len] 只存储了最多的歌曲数,但并不知道这些歌曲到底唱了多少时间。假设最多歌曲数为num, 唱num首歌曲最少时间为tmin, 那么数组中从f[tmin]到f[len]都等于num,我们无法得知唱num首歌的最大时间。比如说len = 10, t[1] = 5, t[2] = 8, 那么f[5] 到 f[10] 都等于1, 无法知道唱从5到10哪个是唱1首歌的最长时间。如何处理呢?

  这里需要用到一个技巧:对决策进行一定的限定!在计算某个时间最多唱的歌曲时,必须是该时间内恰好唱完这些歌,时间多了不行。即f[j]表示的是在j 的时间恰好用完的情况下最多能唱多少首歌。比如上面的例子只有f[5] 和f[8]等于1,其他的都等于0。这样的话处理时先算出最多唱的歌曲数 num,然后从j = len开始遍历数组f, 第一个等于num的就是在最多歌曲情况下的最长时间。

理解起来就是同样数量的值可能会在dp中出现多次所以,歌曲优先级大于时间,于是我们将歌曲数作为背包收益。

如有疑问,欢迎评论指出!

一道令人抓狂的零一背包变式 -- UVA 12563 Jin Ge Jin Qu hao

标签:bre   std   一定的   isp   链接   struct   ostream   如果   动态规划   

原文:https://www.cnblogs.com/mpeter/p/10367446.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号