P2392

发表于 2021-06-03 更新于 2023-12-09 分类于 C,C++ 本文字数： 3.4k 阅读时长 ≈ 6 分钟

P2392 kkksc03考前临时抱佛脚—01背包

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等A1,A2,…,As1，B1,B2,…,Bs2，C1,C2,…,Cs3，D1,D2,…,Ds4。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 2 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 55 行数据：第 11 行，为四个正整数 s*1,s2,s3,s4。

第 22 行，为A1,A2,…,As1 共 s1 个数，表示第一科习题集每道题目所消耗的时间。

第 33 行，为 B1,B2,…,Bs2 共 s2 个数。

第 44 行，为C1,C2,…,Cs3 共 s3 个数。

第 55 行，为 D1,D2,…,Ds4 共 s4 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

1.递归搜索

#include<stdio.h>
int a[21] = {};
int max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}//返回较大值
int lesstime(int i,int m)//i代表第i个习题，m代表剩下的时间
{
    int s;//已安排的时间
    if(i == 0)
        return 0;
    if(m >= a[i])
    {
        int x = lesstime(i - 1, m - a[i]) + a[i]; //放入第i个习题
        int y = lesstime(i - 1, m);//不放入第i个习题
        s = max(x, y);
    }
    else
    {
        s = lesstime(i - 1, m);
    }
    return s;
}//递归搜索求最优解，得到小于时间总数1/2的最大时间
int main()
{
    int s[4];
    scanf("%d%d%d%d", &s[0], &s[1], &s[2], &s[3]);
    int sum = 0;
    int i, j;
    int sums = 0;
    for (i = 0; i < 4; i++)
    {
        for (j = 1; j <= s[i]; j++)
        {
            scanf("%d", &a[j]);
            sum += a[j];
        }
        sums += sum - lesstime(s[i], sum / 2); //求得最靠近sum/2的时间，是最优解
        sum = 0;//重新计数
    }
    printf("%d", sums);
    return 0;
}

递归在多个情况下剩余时间相同时，会反复查找多次，重复计算节点。

2.动态规划

1
2
3

推导公式f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i])
f[i][j],i代表一共有i个习题,j代表最大时间
从i-1个习题到i个习题,可以装也可以不装,按照价值最大的方案装。

#include<stdio.h>
int a[21] = {};
int f[21][10000] = {};
int max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}//返回较大值
int lesstime(int i,int m)//i代表i个习题，m代表最大时间
{
    int p, q;
    for (q = 1; q <= i; q++)
    {
        for (p = 1; p <= m; p++)
        {
            if(a[q]<=p)//可以放下
            {
                f[q][p] = max(f[q - 1][p], f[q - 1][p - a[q]] + a[q]);//求得最优解
            }
            else//放不下
                f[q][p] = f[q - 1][p];
        }
    }
    return f[i][m];
}
int main()
{
    int s[4];
    scanf("%d%d%d%d", &s[0], &s[1], &s[2], &s[3]);
    int sum = 0;
    int i, j;
    int sums = 0;
    for (i = 0; i < 4; i++)
    {
        for (j = 1; j <= s[i]; j++)
        {
            scanf("%d", &a[j]);
            sum += a[j];
        }
        sums += sum - lesstime(s[i],sum/2); //求得最靠近sum/2的时间，是最优解
        //重新计数
        printf("f[%d][%d]=%d\n",s[i],sum/2,lesstime(s[i],sum/2));
        sum = 0;
    }
    printf("%d", sums);
    return 0;
}

动态规划在数据较多的情况下运行效率一般比递归搜索高，动态规划可重新递推求得最优解的组成

1	如果f[i][m] = f[i-1][m],则第i个物品未被装入，否则被装入。

动态规划空间优化

优化后前一次数据被覆盖导致无法求得最优解组成。

每次推导下一轮数据时需要上一轮循坏数据，所以必须倒序推，否则会修改前面的数据，导致这次循环数据使用的本轮循坏数据，即

1 2	f[i][j]=max(f[i-1][j],f[i][j-a[i]]+a[i]);(wrong) f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i])(right)

#include<stdio.h>
int a[21] = {};
int max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}//返回较大值
int lesstime(int i,int m)//i代表i个习题，m代表剩下的时间
{
    int f[10000] = {};
    int p, q;
    for (q = 1; q <= i; q++)
    {
        for (p = m; p >= 0; p--)
        {
            if(a[q]<=p)//可以放下
            {
                f[p] = max(f[p], f[p - a[q]] + a[q]); //求得最优解
            }
            else//放不下
                f[p] = f[p];
        }
    }
    return f[m];
}
int main()
{
    int s[4];
    scanf("%d%d%d%d", &s[0], &s[1], &s[2], &s[3]);
    int sum = 0;
    int i, j;
    int sums = 0;
    for (i = 0; i < 4; i++)
    {
        for (j = 1; j <= s[i]; j++)
        {
            scanf("%d", &a[j]);
            sum += a[j];
        }
        sums += sum - lesstime(s[i],sum/2); //求得最靠近sum/2的时间，是最优解
        //重新计数
        //printf("f[%d]=%d\n",sum/2,lesstime(s[i],sum/2));
        sum = 0;
    }
    printf("%d", sums);
    return 0;
}