牛客NC320 装箱问题【中等 动态规划,背包问题 C++/Java/Go/PHP】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/d195a735f05b46cf8f210c4ad250681c

几乎完全相同的题目:
https://www.lintcode.com/problem/92/description

思路

动态规划都是递归递推而来。php答案是动态规划版本,递归版本有
测试用例超时,C++/.JAVA/GO 递归版本能通过所有测试用例

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型vector
     * @return int整型
     */
    int boxin(int V, vector<int>& num) {
        int maxStore = dfs(num, 0, V);
        return V - maxStore;
    }

    int dfs(vector<int>& arr, int idx, int rest) {
        if (rest < 0) return -1;
        if (idx == arr.size()) {
            return 0;
        }

        int p1 = dfs(arr, idx + 1, rest);
        int p2 = 0;
        int next = dfs(arr, idx + 1, rest - arr[idx]);
        if (next != -1) {
            p2 = next + arr[idx];
        }

        if (p1 > p2) {
            return p1;
        }
        return p2;
    }
};

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型ArrayList
     * @return int整型
     */
    public int boxin (int V, ArrayList<Integer> num) {
        int maxstore  = dfs(num, 0, V);
        return V - maxstore;
    }

    public int dfs(ArrayList<Integer> ll, int idx, int rest) {
        if (rest < 0)
            return -1;

        if (idx == ll.size()) {
            return 0;
        }

        int p1 = dfs(ll, idx + 1, rest);
        int p2 = 0;
        int next = dfs(ll, idx + 1, rest - ll.get(idx));
        if (next != -1) {
            p2 = next + ll.get(idx);
        }

        return Math.max(p1, p2);

    }
}

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param V int整型
 * @param num int整型一维数组
 * @return int整型
 */
func boxin(V int, num []int) int {
maxStore := dfs(num, 0, V)
	return V - maxStore
}

func dfs(num []int, idx int, rest int) int {
	if rest < 0 {
		return -1
	}

	if idx == len(num) {
		return 0
	}

	p1 := dfs(num, idx+1, rest)
	p2 := 0

	next := dfs(num, idx+1, rest-num[idx])

	if next != -1 {
		p2 = next + num[idx]
	}

	if p1 > p2 {
		return p1
	}
	return p2
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param V int整型 
 * @param num int整型一维数组 
 * @return int整型
 */
function boxin( $V ,  $num )
{
        $n = count($num);
    $dp=[];
    for($i=0;$i<=$n;$i++){
        for($j=0;$j<=$V;$j++){
            $dp[$i][$j] = 0;
        }
    }

    for($i=$n-1;$i>=0;$i--){
        for($rest = 0;$rest<=$V;$rest++){
            $p1 = $dp[$i+1][$rest];
            $p2 =0;
            $next = $rest-$num[$i] <0 ? -1: $dp[$i+1][$rest-$num[$i]];
            if($next!=-1){
                $p2 = $next+$num[$i];
            }
            $dp[$i][$rest] = $p1>$p2? $p1:$p2;
        }
    }

    return $V- $dp[0][$V];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/583107.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ios CI/CD 持续集成 组件化专题五-(自动发布私有库-组件化搭建)

一&#xff1a;手动发布私有库总结 手动发布pod私有库&#xff0c;需要进行如下几步操作&#xff1a; 1、修改完代码之后&#xff0c;需要提交代码push到git仓库。 2、给代码打tag。 3、修改podspec文件的version值&#xff0c;使其和设置的tag一直。 4、命令行执行pod repo…

【蓝桥杯省赛真题41】python搬运物品方案 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

目录 python搬运物品方案 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python搬运物品方案 第十三届蓝桥杯青少年组python省赛比赛 一、题目…

【CGALDotNet】二维矢量多边形可视域计算(C#调用CGAL)

参考 CGALDotNet快速开始&#xff1a;https://blog.csdn.net/liqian_ken/article/details/138274933 CGAL二维可视域计算介绍&#xff1a;https://doc.cgal.org/latest/Visibility_2/index.html#visibility_2_introduction CGAL相关接口&#xff1a;https://doc.cgal.org/late…

明日周刊-第8期

现在露营的人越来越多了&#xff0c;都是带着帐篷或者遮阳篷聚在一起喝喝茶聊聊天&#xff0c;这是一种很好的放松方式。最近我养了一只金毛&#xff0c;目前两个月大&#xff0c;非常可爱。 文章目录 一周热点资源分享言论歌曲推荐 一周热点 一、人工智能领域 本周&#xff…

2024.4.29

模板类实现顺序栈 #include <iostream>using namespace std; template <typename T> class Seqlite{T data[30];int len0; public:void head_inst(T date);void head_dele();void show(); }; template <typename T> //头插函数 void S…

如何快速申请SSL证书实现HTTPS访问?

申请SSL证书最简单的方法通常涉及以下几个步骤&#xff0c;尽量简化了操作流程和所需专业知识&#xff1a; 步骤一&#xff1a;选择适合的SSL证书类型 根据您的网站需求&#xff0c;选择最基础的域名验证型&#xff08;DV SSL&#xff09;证书&#xff0c;它通常只需验证域名所…

OpenAI 新推出 AI 问答搜索引擎——SearchGPT 震撼登场

您的浏览器不支持 video 标签。 OpenAI-SearchGPT 近日&#xff0c;OpenAI 曝光了自己的一款令人瞩目的 AI 问答搜索引擎——SearchGPT。这款搜索引擎带来了全新的搜索体验&#xff0c;给整个行业带来了巨大的压力。 SearchGPT 支持多种强大的功能。首先&#xff0c;它能够通过…

新一代状态空间模型网络替代Transformer 综述

本文首先初步介绍了状态空间模型&#xff08;SSM&#xff09;的工作原理。然后&#xff0c;从多个方面回顾SSM的相关工作&#xff0c;包括SSM的起源和变化、自然语言处理、计算机视觉、图、多模态处理、多模态和多媒体、点云/事件流数据、时间序列数据等领域的相关工作。 此外…

网络安全设计的技术有哪些?

目录 1. 防火墙 2. 入侵检测系统&#xff08;IDS&#xff09;和入侵防御系统&#xff08;IPS&#xff09; 3. 身份和访问管理&#xff08;IAM&#xff09; 4. 数据加密 5. 网络分割和虚拟化 6. 安全信息和事件管理&#xff08;SIEM&#xff09; 7. 端点保护 8. 配置管理…

链表带环问题的方法证明

目录 一、带环问题的解决 1、固定思路 2、思路后的数学证明 3、不相遇的情况分析 二、环入口问题 ​编辑 1、固定思路 2、数学证明 三、求环的长度 一、带环问题的解决 1、固定思路 链表带环问题比较传统的思路是使用快慢指针&#xff0c;当快和慢指针相遇的时候那么…

工具篇--Window--常用工具命令汇总(持续更新)

文章目录 前言一、常用工具&#xff1a;1.1 window host 修改&#xff1a;1.2 window 端口占用&#xff1a;1.3 打开/关闭防火墙&#xff1a;1.4 JavaScript 对象或值转换为 JSON 字符串: 二、命令行&#xff1a;2.1 获取本机ip&#xff1a; 三、网页在线工具&#xff1a;3.1 本…

吴恩达深度学习笔记:深度学习的 实践层面 (Practical aspects of Deep Learning)1.9-1.10

目录 第一门课&#xff1a;第二门课 改善深层神经网络&#xff1a;超参数调试、正 则 化 以 及 优 化 (Improving Deep Neural Networks:Hyperparameter tuning, Regularization and Optimization)第一周&#xff1a;深度学习的 实践层面 (Practical aspects of Deep Learning)…

LabVIEW自动剪板机控制系统

LabVIEW自动剪板机控制系统 随着工业自动化的快速发展&#xff0c;钣金加工行业面临着生产效率和加工精度的双重挑战。传统的手动或脚踏式剪板机已无法满足现代生产的高效率和高精度要求&#xff0c;因此&#xff0c;自动剪板机控制系统的研究与开发成为了行业发展的必然趋势。…

如何快速开发个性化回收小程序

回收小程序的开发无疑是提升回收业务效率的重要途径。它不仅可以清晰地列出各类回收物品&#xff0c;还能在微信、抖音、支付宝等多个平台同时上线&#xff0c;让回收服务触手可及。那么&#xff0c;如何以最快、最简单、最经济的方式上线这样一个小程序呢&#xff1f; 在这里&…

Linux实训-用户和组的管理

实训1&#xff1a;用户的管理 创建一个新用户user1&#xff0c;设置其主目录为/home/user1。查看/etc/passwd文件的最后一行&#xff0c;看看是如何记录的。查看文件/etc/shadow文件的最后一行&#xff0c;看看如何记录的。给用户user1设置密码。再次查看文件/etc/shadow文件的…

分享5个图源二维码及使用方法

数据是GIS的血液&#xff01; 我们在《4个在ArcGIS中可加载的图源分享》一文中&#xff0c;为大家分享了4个可以直接在ArcMap中打开查看的图源。 现在&#xff0c;我们再分享5个可以在水经微图&#xff08;以下简称“微图”&#xff09;桌面版&#xff08;PC端&#xff09;、…

Kafka Exactly Once 语义实现原理:幂等性与事务消息

01 前言 在现代分布式系统中&#xff0c;确保数据处理的准确性和一致性是至关重要的。Apache Kafka&#xff0c;作为一个广泛使用的流处理平台&#xff0c;提供了强大的消息队列和流处理功能。随着业务需求的增长&#xff0c;Kafka 的事务消息功能应运而生&#xff0c;它允许应…

MacPro(M1,M2芯片)Java开发和常用工具开源软件合集

目录 Java开发软件1 IDE1.1 idea1.2 Vs Code 2 开发工具2.1 数据库数据库模型管理数据库连接客户端 2.2 SSH/Telnet/Serial/Shell/Sftp客户端2.3 MarkDown编辑器2.3 代码片段管理粘贴 3小工具3.1 截图贴图3.2 Mac下修改hosts文件的图形化界面软件 Java开发软件 1 IDE 1.1 ide…

第三方软件测试机构-科技成果评价测试

科技成果评价测试是对科研成果的工作质量、学术水平、实际应用和成熟程度等方面进行的客观、具体、恰当的评价过程。这一评价过程有助于了解科技成果的质量和水平&#xff0c;以及其在学术和应用方面的价值和潜力。 科技成果评价测试主要包括以下几个方面&#xff1a; 工作质量…

设计不外流,保护创意的同时锁住图纸安全!

在设计行业中&#xff0c;图纸和创意文稿的安全至关重要&#xff0c;因为它们体现了企业的创新能力和核心竞争力。华企盾DSC数据防泄密系统提供了一系列功能&#xff0c;可以有效地保护这些珍贵的设计和文档不被外泄。以下是如何利用华企盾DSC系统保障设计图纸安全的关键措施&a…