首页 > 其他分享 >西农OJ P1005 装载问题

西农OJ P1005 装载问题

时间:2023-08-20 16:22:55浏览次数:36  
标签:西农 OJ weight int sum P1005 测例 c2 c1

装载问题

问题描述

有两艘船,载重量分别是c1、 c2,n个集装箱,重量是wi (i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。

输入

多个测例,每个测例的输入占两行。第一行一次是c1、c2和n(n<=10);第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。

输出

对于每个测例在单独的一行内输出Yes或No。

样例输入

7 8 2
8 7
7 9 2
8 8
0 0 0

样例输出

Yes
No

解题思路

先计算出 c1 能放下的最大值 max , 若 c2-max >= 0 ,则能装下.

公式

\( f(c,n) = min\{f(c,n-1),f(c-w[n],n-1)\} \)

其中 w 为 weight 集合.

公式计算背包容量剩余c,且剩余n个物品时, 最优解剩余的背包容量.

递归终点

物品数为0,或者背包装不下

我的代码

#include<iostream>
#define NaN 114514

using namespace std;

int min(int,int);
int f(int,int,int[]);

int main(){
    while(1){
        // sum 物品重量总和, weight 记录装入c1的最大值.
        int c1,c2,n,sum = 0,weight;
        cin >> c1 >> c2 >> n;
        if( n == 0 ){
            break;
        }
        int w[n];
        for(int i = 0; i < n; i++){
            cin >> w[i];
            sum += w[i]; // 计算中重量
        }
        weight = c1 - f(c1,n,w); // 装入c1的总重量
        if( sum - weight <= c2 ){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}

int min(int a,int b){
    return a<b?a:b;
}

int f(int c,int n,int w[]){
    if( c < 0 ){ // 如果装不下
        return NaN; // 返回无穷大
    }
    if( n == 0 ){ // 如果没有物品了
        return c; // 直接返回背包剩余容量
    }
    int i = n-1; //下标
    return min(f(c,n-1,w),f(c-w[i],n-1,w));
}

标签:西农,OJ,weight,int,sum,P1005,测例,c2,c1
From: https://www.cnblogs.com/orzmiku/p/17644159.html

相关文章

  • 西农OJ P1491 城市电话号码
    题目描述某城市电话号码包括地区码、前缀、有效号码三部分组成,其中地区码是0-4位数字;前缀是以非0开头的3位数字,有效号码是4位数字,各部分之间用减号(-)分隔,地区码为空时地区码与前缀之间不包含分隔符。请编写函数检测输入号码num的有效性,若输入号码符合上述规定返回0,否则返回1。函......
  • 8-20|https://gitlab.xx.com/api/v4/projects/4/trigger/pipeline Request failed 状
    当你使用GitLabAPI并收到状态码400,这通常意味着你发送的请求是“坏的”或格式不正确。以下是一些建议,帮助你解决问题:1.**验证请求正文**:确保你提供的请求正文(如果有的话)是正确的并符合API的预期格式。对于触发管道的API,你可能需要提供有关分支、变量等的信息。2.**检查URL*......
  • [HZOJ普及模拟2]
    \(\Huge\color{7ff77f}{打了一场模拟赛,又垫底了。qwq}\)\(\Huge\color{12f4ff}{快}\)\(\Huge\color{f9f98f}{V}\)\(\Huge\color{ff1256}{本}\)\(\Huge\color{ff4514}{蒟}\)\(\Huge\color{7ffff7}{蒻}\)\(\Huge\color{3f3f3f}{5}\)\(\Huge\color{f54321......
  • [转]By not providing "FindEigen3.cmake" in CMAKE_MODULE_PATH this project has
    在编译安装的时候出现如下问题,是Eigen3的Cmake依赖问题,已经安装eigen3,但在项目的find_package(Eigen3QUERIED)中,无法找到FindEigen3.Cmake. CMakeErroratloam_velodyne/CMakeLists.txt:13(find_package):Bynotproviding"FindEigen3.cmake"inCMAKE_MODULE_......
  • QOJ # 6504. Flower's Land 2
    题面传送门感觉,非常高妙的随机化!考虑怎么判定一个序列合法,将每种颜色的奇数位置看成左括号,偶数位置看成右括号,则一个序列合法当且仅当其括号序列合法。现在带修,我们维护的东西需要满足如下性质:可逆:将相邻奇数位的信息和偶数位的信息合并需要等于单位元。有结合律:不然没有办......
  • protojson简介
    google.golang.org/protobuf/encoding/protojson是Go语言中的一个库,用于处理ProtocolBuffers(protobuf)和JSON之间的转换,遵循https://protobuf.dev/programming-guides/proto3#json实现。以下是该库的一些主要功能:将protobuf消息转换为JSON格式:这是通过Marshal或Ma......
  • tfs 迁入解决方案缺少项目文件[*.csproj]
    .csproj、.vssscc没办法签入TFS怎么办?试图将VisualStudio文件上传到TeamFoundationServer中,但是签入了解决方案文件,项目文件一个都没签入,没办法,就右键,手工将文件添加到源代码管理器。但是.csproj、.vssscc并没有在VisualStudio的解决方案资源管理器中出现,怎么将......
  • 【JZOJ7839】神秘代码
    凯尔希我谢谢你lcp的题所以考虑使用$SA$或者$SAM$此处使用大佬提供的$SA$思路PartI首先我们考虑不反转怎么做这其实是一道SA板子题我们将所有的字符串全部用特殊符号隔开变成一个大字符串然后把每个点的$height$数组跑出来对于每一个点的$height$值......
  • SpringBoot操作前端传的Geojson进行空间查询
    SpringBoot操作前端传的Geojson进行空间查询项目说明:项目技术栈:SpringBoot+MybatisPlus+postgresql先上查询SQLSELECT*FROMdemoWHEREST_Intersects(geom,ST_GeomFromGeoJSON('放geojson类型数据'));表结构Controller层packagecom.itcy.postgresql.controller;importco......
  • formDataToJSON 抽丝剥茧 formData 与 Object 的转换【玩转源码】
    前言通过axios源码阅读,实现formDataToJSON抽丝剥茧formData与Object的转换,接下来详细分享整个过程。formDataToJSON抽丝剥茧formData与Object的转换FormData对象FormData对象用以将数据编译成键值对,以便用XMLHttpRequest来发送数据。FormData对象主要用于发送表单数......