01背包补题(一)(下)

简介: 01背包补题(一)

P1926 小书童——刷题大军

本题链接:P1926 小书童——刷题大军

本博客给出本题截图:

62.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 160, M = 15;
int f[N];    // 在用时不超过 i 的情况下获得的最大得分
int v[M];
int vh[M], wh[M];
int main()
{
    int n, m, k, r;
    cin >> n >> m >> k >> r;
    for (int i = 1; i <= n; i ++ ) cin >> v[i];
    for (int i = 1; i <= m; i ++ ) cin >> vh[i];
    for (int i = 1; i <= n; i ++ ) cin >> wh[i];
    sort(v + 1, v + n + 1);    // 贪心,优先去做耗时较少的题目
    for (int i = 1; i <= n; i ++ )
        for (int j = r; j >= vh[i]; j -- )
            f[j] = max(f[j], f[j - vh[i]] + wh[i]);
    for (int i = 1; i <= r; i ++ )
        if (f[i] >= k)
        {
            r -= i;
            break;
        }
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (r >= v[i])
        {
            r -= v[i];
            cnt ++;
        }
    cout << cnt << endl;
    return 0;
}

P1802 5 倍经验日

本题链接:P1802 5 倍经验日

本博客给出本题截图:

63.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1010;
LL f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        int l, w, v;
        cin >> l >> w >> v;
        for (int j = m; j >= 0; j--)
        {
            if (j >= v) f[j] = max(f[j] + l, f[j - v] + w);
            else f[j] = f[j] + l;
        }
    }
    cout << 5 * f[m] << endl;
    return 0;
}

P1734 最大约数和

本题链接:P1734 最大约数和

本博客给出本题截图:

64.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N];
int f[N];
int main()
{
    int n;
    cin >> n;
    // 预处理w数组
    for (int i = 1; i <= n / 2; i ++ )
        for (int j = 2; i * j <= n; j ++ )
            w[i * j] += i;
    for (int i = 1; i <= n; i ++ )
        for (int j = n; j >= i; j -- )
            f[j] = max(f[j], f[j - i] + w[i]);
    cout << f[n] << endl;
    return 0;
}

P2392 kkksc03考前临时抱佛脚

本题链接:P2392 kkksc03考前临时抱佛脚

本博客给出本题截图:

65.png

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 610, M = 20;
int s[5];
int w[M];
int f[N];
int main()
{
    for (int i = 1; i <= 4; i ++ ) cin >> s[i];
    int res = 0;
    for (int i = 1; i <= 4; i ++ )
    {
        int sum = 0;
        memset(f, 0, sizeof f);
        for (int j = 1; j <= s[i]; j ++ ) cin >> w[j], sum += w[j];
        int m = sum / 2;
        for (int j = 1; j <= s[i]; j ++ )
            for (int k = m; k >= w[j]; k -- )
                f[k] = max(f[k], f[k - w[j]] + w[j]);
        res += max(f[m], sum - f[m]);
    }
    cout << res << endl;
    return 0;
}

总结

题目比较灵活,有时需要进行预处理,有时需要加上贪心的策略。

目录
相关文章
|
测试技术 API 数据库
性能测试概念
**性能测试评估系统在负载下的表现,关注响应时间、吞吐量、并发用户数和资源利用率。关键指标包括RT、HPS、TPS、QPS、RPS等。并发数可由QPS和平均响应时间计算。提升压力的技术手段涉及多进程、多线程,各有优劣。P90、P95、P99等分位数用于描述数据分布,揭示不同负载场景下的系统性能。**
|
JavaScript 前端开发 算法
在JavaScript中实现的基本AABB矩形碰撞检测用于2D游戏
【5月更文挑战第14天】在JavaScript中实现的基本AABB矩形碰撞检测用于2D游戏,涉及Rectangle类,包含x,y,width和height属性,以及一个检测碰撞的collidesWith方法。该方法通过比较矩形边界来判断是否相交,返回布尔结果。示例代码展示了如何检测两个Rectangle实例是否发生碰撞。更复杂的场景可能需使用高级算法或物理引擎库。
494 3
|
存储 数据库
医学影像信息(PACS)系统软件源码
医学影像信息(PACS)系统软件源码
433 1
|
Ubuntu 网络虚拟化 Windows
国产化之虚拟ARM64-CPU安装银河麒麟操作系统
国产化之虚拟ARM64-CPU安装银河麒麟操作系统
6317 0
|
XML Java 数据格式
SpringIOC精讲
SpringIOC精讲
205 0
|
存储 NoSQL 架构师
Volvo Connect 利用MongoDB 提升数据库效率
提升追踪6,500 万起日常事件时的数据库效率
|
机器学习/深度学习 智能设计 自然语言处理
Gradient Normalization在多任务学习中的优化实践
在每平每屋以及我们团队负责的其他一些场景,MMoE多任务模型是精排阶段常用的模型。在每平每屋场景中,我们使用MMoE模型,对场景中的三个任务同时进行点击率预估,即内容的一跳点击、内容详情页点击以及跳转的商品详情页点击。
1780 0
Gradient Normalization在多任务学习中的优化实践
|
前端开发 开发者
React 组件的 children 数据使用
React 组件的 children 数据使用
354 0
|
弹性计算 对象存储 CDN
阿里云账号实名认证教程方法(快速实名)
阿里云账号注册后要通过实名认证才可以购买云服务器、对象存储OSS、CDN、域名等产品,阿里云百科以个人是名人未来,里
2547 0
阿里云账号实名认证教程方法(快速实名)