小米OJ #24题 海盗分赃 #27石头收藏家

2024-01-21 03:50

本文主要是介绍小米OJ #24题 海盗分赃 #27石头收藏家,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 描述:
    一箱失落多年的宝藏被两位海盗找到,宝箱里的一堆大小与重量各不相同的金块。 他们称出了每个金块的重量,但是如何如何平分这些金子却令他们十分头疼。 程序员们,你能告诉两位海盗,他们能否平分这箱宝藏么?假设宝箱里有三块金子,重量分别为:1,2,3。则他们可以平分这些金子:1+2=3 又假设宝箱里有四块金子,重量分别为:1,2,6,4。则他们无法找到平分的方法。
  • 输入:
    一行由逗号分隔的 N 个无序正整数(0<N<100),每个正整数表示每块金子的重量 。W(0<W<10000)。
  • 输出:
    字符串true或false,表示海盗们能否平分这些金子。
  • 输入样例:
1,2,3
1,2,6,4
1,6,8,3,5,9
10,5,8,6,20,13,7,11
  • 输出样例:
true
false
true
true

说明:
1:和小米OJ中的27题石头收藏家解法一摸一样,使用动态规划进行求解。
2:首先如果黄金总重量加起来是奇数,则不管怎么分两个人都不能分一样

if((all_weight)%2) {printf("false");return 0;} 

3:如果所有的黄金重量加起来是偶数,这时候就需要进行动态规划处理:
(1):如果可以分,肯定是一人一半,所以先拿出一半的黄金重量。这时候假设背包的最大容量max_capacity=一半的黄金重量,只要在题目给定的黄金中,找到一些黄金,把背包填满就行。

(2):为了方便大家理解,把该问题转化为01背包问题;使得黄金的重量和黄金的价值相等,即1重量的黄金价值也为1,2重量的黄金价值为2,…
(3):典型的0-1背包问题(和小米OJ27题非常相似):在给定背包容量的前提下,尽可能装更多价值的黄金。最后判断所计算出来的最大价值是不是等于黄金总重量的一半即可。(注意:黄金的价值和重量相当,计算出来的最大价值也就是最大重量,只要满足总重量的一半,就可以平分。)
(4):对于此类问题中二维dp数组不好理解的,可以利用0/1背包在线求解网站辅助理解(http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html)。
使用测试数据中的第三行:1,6,8,3,5,9
该数据的一半是16,最后求得的数据是16
下面给出海盗分赃代码和石头收藏家代码,省的再写一篇了:
海盗分赃

// xiaomiOJ_24.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
#include<string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;
char gold[10000];
int dp[10000][10000] = { 0 };
int a[100000] = { 0 };
int main()
{int  sum = 0, k = 1;int  num = 0, max_capacity = 0, last_result = 0;gets_s(gold);                                      //读入字符串for (int i = 0; i < strlen(gold); i++) {if (gold[i] == ',') {k++;continue;}else a[k] = a[k] * 10 + gold[i] - '0';}                                             //转换成int数组,放在a中,第一元素置为0。for (int j = 0; j <= k; j++) {sum = sum + a[j];}                                               //求和if (sum % 2) {                        printf("false");return 0;}                                             //奇数判断num = k, max_capacity = sum / 2;for (int i = 1; i <= num; i++) {for (int j = 1; j <= max_capacity; j++) {if (j < a[i]) {dp[i][j] = dp[i - 1][j];}else{dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);}last_result = MAX(last_result, dp[i][j]);}}                                          //dp结束,后面是判断结果是否为一半if (last_result == (sum / 2)) printf("true");else  printf("false");return 0;
}

程序没优化,将就着看看把~~
石头收藏家

#include <iostream>
#include<stdio.h>
#include<string.h>
#pragma warning(disable:4996)
#define MAX(a,b) (a>b?a:b)
int  last_result = 0;
using namespace std;
int dp[1000][1000] = { 0 };
int main()
{char character;int  a[2][60] = {0}, i = 0, j = 0, num = 0;int max_value = 0, max_capacity = 0;(void)scanf("%d", &max_capacity);while (~scanf("%d%c", &num, &character)) {a[0][++i] = num;if (character == '\n') break;}i = 0;num = 0;while (~scanf("%d%c", &num, &character)) {a[1][++i] = num;if (character == '\n') break;}                                           //需要说明a的第一行存的重量,第二行存的是价值num = i;   //将石头个数也就是数组长度赋给num;//不需要排序,直接使用动态规划进行求解for (int i = 1; i <= num; i++) {for (int j = 1; j <= max_capacity; j++) {if (j < a[0][i]) {dp[i][j] = dp[i - 1][j];}else{dp[i][j] = MAX(dp[i-1][j],dp[i-1][j-a[0][i]]+a[1][i]);}last_result = MAX(last_result, dp[i][j]);}}printf("%d", last_result);return 0;
}

代码通过了就没管了,如有问题欢迎大家指出!

这篇关于小米OJ #24题 海盗分赃 #27石头收藏家的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/628299

相关文章

百度/小米/滴滴/京东,中台架构比较

小米中台建设实践 01 小米的三大中台建设:业务+数据+技术 业务中台--从业务说起 在中台建设中,需要规范化的服务接口、一致整合化的数据、容器化的技术组件以及弹性的基础设施。并结合业务情况,判定是否真的需要中台。 小米参考了业界优秀的案例包括移动中台、数据中台、业务中台、技术中台等,再结合其业务发展历程及业务现状,整理了中台架构的核心方法论,一是企业如何共享服务,二是如何为业务提供便利。

树莓派5_opencv笔记27:Opencv录制视频(无声音)

今日继续学习树莓派5 8G:(Raspberry Pi,简称RPi或RasPi)  本人所用树莓派5 装载的系统与版本如下:  版本可用命令 (lsb_release -a) 查询: Opencv 与 python 版本如下: 今天就水一篇文章,用树莓派摄像头,Opencv录制一段视频保存在指定目录... 文章提供测试代码讲解,整体代码贴出、测试效果图 目录 阶段一:录制一段

Science|癌症中三级淋巴结构的免疫调节作用与治疗潜力|顶刊精析·24-09-08

小罗碎碎念 Science文献精析 今天精析的这一篇综述,于2022-01-07发表于Science,主要讨论了癌症中的三级淋巴结构(Tertiary Lymphoid Structures, TLS)及其在肿瘤免疫反应中的作用。 作者类型作者姓名单位名称(中文)通讯作者介绍第一作者Ton N. Schumacher荷兰癌症研究所通讯作者之一通讯作者Daniela S. Thomm

安卓玩机工具------小米工具箱扩展工具 小米机型功能拓展

小米工具箱扩展版                     小米工具箱扩展版 iO_Box_Mi_Ext是由@晨钟酱开发的一款适用于小米(MIUI)、多亲(2、2Pro)、多看(多看电纸书)的多功能工具箱。该工具所有功能均可以免root实现,使用前,请打开开发者选项中的“USB调试”  功能特点 【小米工具箱】 1:冻结MIUI全家桶,隐藏状态栏图标,修改下拉通知栏图块数量;冻结

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构:字节 ➡️领域: Information systems → Data management systemsStorage management 📚摘要:介绍了字节新提出的ByteGraph 3.0(BG3)模型,用来处理大规模图结构数据 背景

【A题成品论文已出】24数学建模国赛A题成品论文(附参考代码)免费分享

A 题  “板凳龙”  闹元宵 摘要 “板凳龙”是一种传统的民俗文化活动,通常由许多板凳连接成龙的形状进行表演。本文基于螺旋线和板凳龙的运动特性,建立数学模型来分析舞龙队在不同情况下的运动轨迹、调头路径和速度优化等问题。问题主要涉及板凳龙的行进路径、碰撞避免、调头空间的设计,以及如何优化龙头的速度,以确保龙身与龙尾的行进安全。 针对问题一,舞龙队由223节板凳组成,龙头前把手的速度为1

【Git 学习笔记_24】Git 使用冷门操作技巧(四)——更多实用 git 别名设置、交互式新增提交

文章目录 11.8 更多别名设置别名1:只查看当前分支(git b)别名2:以图表形式显示自定义格式的 git 日志(git graph)别名3:查看由于合并分支导致的冲突后仍有冲突的、待合并的文件列表(git unmerged)别名4:查看 git 状态(git st)别名5:查看 git 简要状态(git s)别名6:查看最新版本的统计信息(git l1)别名7:查看最近 5 个版本的提

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

大厂面试:小米嵌入式面试题大全及参考答案(130+道 12万长文)

Flink 架构介绍 Flink 是一个分布式流处理和批处理框架,具有高吞吐、低延迟、高可靠等特点。其架构主要由以下几个部分组成: 客户端(Client):负责将作业提交到集群,并与作业管理器进行交互,获取作业的状态信息。客户端可以是命令行工具、IDE 插件或者自定义的应用程序。作业管理器(JobManager):负责接收客户端提交的作业,协调资源分配,调度任务执行,并监控作业的执

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in