01背包补题(一)(中)

简介: 01背包补题(一)

P1164 小A点菜

本题链接P1164 小A点菜

本博客给出本题截图

58.png


#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- )
            f[j] += f[j - v];
    }
    cout << f[m] << endl;
    return 0;
}

P1510 精卫填海

本题链接P1510 精卫填海

本博客给出本题截图

59.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int v[N], w[N];
int f[N];
int main()
{
    int m, n, c;
    cin >> m >> n >> c;
    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = c; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    if (f[c] < m) cout << "Impossible" << endl;
    else
        for (int i = 0; i <= c; i ++ )
            if (f[i] >= m)
            {
                cout << c - i << endl;
                break;
            }
    return 0;
}

P2639 [USACO09OCT]Bessie’s Weight Problem G

本题链接P2639 [USACO09OCT]Bessie’s Weight Problem G

本博客给出本题截图

60.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 45010;
int f[N];
int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + v);
    }
    cout << f[m] << endl;
    return 0;
}

P2925 [USACO08DEC]Hay For Sale S

本题链接P2925 [USACO08DEC]Hay For Sale S

本博客给出本题截图

61.png

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
int f[N];
int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + v);
    }
    cout << f[m] << endl;
    return 0;
}


目录
相关文章
28个残疾人,两个月,被阿里客服改变的命运
十年里,阿里巴巴云客服累计免费培训了35万人,为11万人提供了就业岗位,这28个残疾人也正是这11万人中的一份子。
28个残疾人,两个月,被阿里客服改变的命运
|
Unix Shell 测试技术
误删数据恢复系列1
误删数据恢复系列1
251 0
|
iOS开发
iOS 启动图设置及icon图标设置
OS 启动图设置及icon图标设置
1056 0
iOS 启动图设置及icon图标设置
SAP事务码MM17物料主数据批量维护
这个事务码真的很有意思,因为可以看到物料主数据不同层次的内容。为什么这么说呢?进入MM17
2681 0
|
Java 数据库连接 数据库
信不信十分钟让你彻底搞懂java反射
概念:反射是Java的一种机制,让我们可以在运行时获取类的信息 作用:通过反射,我们可以在程序运行时动态创建对象,还能获取到类的所有信息,比如它的属性、构造器、方法、注解等;
18378 2
信不信十分钟让你彻底搞懂java反射
|
Dart 开发工具 Android开发
Mac OS 配置 Flutter 开发环境
手把手教你如何在 Mac OS 下配置 Flutter 开发环境。
1459 0
Mac OS 配置 Flutter 开发环境
|
算法 数据处理 数据库
TCGA数据库的利用(三)—做差异分析的三种方法
今天更新TCGA数据库的利用系列第三篇文章,在对TCGA数据进行挖掘时,通常会筛选出来一些表达量显著异常的基因,作为后续研究的对象,这个筛选过程叫做差异分析;本篇文章将分为三大模块对差异分析进行介绍
|
Web App开发 存储 前端开发
字母a的6种表示方法,以及其背后的编码知识
字符是我们编写程序的基础的基础。 我们前端是最常见的字符,符号,数字,英文,中文, 我们通常都是使用直接量来表示,偶尔会在正则表达等场景用到UTF-16码点的格式,问题来了,那你知道JS有几种字符表示方式吗?
1408 0
字母a的6种表示方法,以及其背后的编码知识
|
存储 前端开发 JavaScript
为什么我使用 Umi 的 model 简易数据流管理插件
Umi 是一款企业级的 React 前端应用框架,云巧产业数字组件中心推荐使用基于 Umi 的 Koi 框架统一前端应用研发流程,支撑前端项目从研发、联调到上线、发布的全流程。 本文假设您正在或计划使用 Umi 或 Koi 作为底层框架支撑前端应用的开发,并且对 Umi 有一定的了解。 ## 数据治理的原则 React 的核心特征是“数据驱动视图”,用公式表达即 `UI = render(d
|
算法 Java 数据库
过关斩将-终获阿里offer
春招暑期实习,目标岗位Java后台开发,成功斩获阿里云/腾讯云/美团offer,圆梦阿里~
3155 0
过关斩将-终获阿里offer