洛谷 装箱问题 01背包 java

这篇具有很好参考价值的文章主要介绍了洛谷 装箱问题 01背包 java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍑 OJ专栏


🍑 装箱问题

[NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 V V V,同时有 n n n 个物品,每个物品有一个体积。

现在从 n n n 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V V V,表示箱子容量。

第二行共一个整数 n n n,表示物品总数。

接下来 n n n 行,每行有一个正整数,表示第 i i i 个物品的体积。

输出格式

  • 共一行一个整数,表示箱子最小剩余空间。

样例 #1

样例输入 #1

24
6
8
3
12
7
9
7

样例输出 #1

0

提示

对于 100 % 100\% 100% 数据,满足 0 < n ≤ 30 0<n \le 30 0<n30 1 ≤ V ≤ 20000 1 \le V \le 20000 1V20000

【题目来源】

NOIP 2001 普及组第四题

👨‍🏫 把体积也当作价值(要求的最大体积就是最大的价值)文章来源地址https://www.toymoban.com/news/detail-445368.html

import java.util.Scanner;

public class Main
{
	static int N = 20010;
	static int[] f = new int[N];

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		for (int i = 0; i < n; i++)
		{
			int v = sc.nextInt();
			for (int j = m; j >= v; j--)
				f[j] = Math.max(f[j], f[j - v] + v);// 把体积也看成价值
		}

		System.out.println(m - f[m]);// 记得要求输出的最小的剩余空间
	}
}

到了这里,关于洛谷 装箱问题 01背包 java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 背包问题分析代码详解【01背包+完全背包+多重背包】

    一、01背包问题 问题描述: 有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。 朴素01背包 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值 状态转移 1) 选第i个物品:f[i,j] = f

    2024年02月06日
    浏览(40)
  • leetcode刷题之背包问题(01背包)

    01 背包 概念:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是 w e i g h t [ i ] weight[i] w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] value[i] v a l u e [ i ] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 方法1:暴力回溯法 方法2:动态规划 三个

    2024年02月02日
    浏览(50)
  • 01背包问题——以小明的背包1 为例

    本文旨在加强01背包问题的记忆与理解,步骤会细化 小明有一个容量为 VV的背包。 这天他去商场购物,商场一共有 N 件物品,第 i 件物品的体积为 w ,价值为 v 。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少,请你帮他算算。 输入描述 输入第

    2023年04月14日
    浏览(37)
  • 算法训练第四十二天|01背包问题 二维 、01背包问题 一维、416. 分割等和子集

    视频链接:https://www.bilibili.com/video/BV1cg411g7Y6/ 参考:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。 而完全背包又是也是01背包稍作变化而来,即:完全

    2024年02月01日
    浏览(46)
  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(54)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(56)
  • 回溯算法--01背包问题

    目录 回溯算法--01背包问题 [算法描述] [回溯法基本思想] 法一: 法二:  代码:  运行结果 代码改进  0-1背包问题是子集选取问题。一般情况下,0-1背包问题是NP完全问题。0-1背包问题的解空间可以用子集树表示。 解0-1背包问题的回溯法与解装载问题的回溯法十分相似。 在

    2023年04月09日
    浏览(38)
  • 动态规划——01背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 状态表示 :用一个数组 f[][] (数组可能是一维也可能是二维,根据具体题目具体分析)来表示某个集合,这个集合

    2024年02月03日
    浏览(44)
  • 【动态规划】01背包问题

    动态规划是一种非常常见的算法,不论是在我们平时刷题的过程中还是在竞赛中,总会见到动态规划的身影,而动态规划又分为很多种,其中01背包问题是非常典型的一类动态规划问题。如果大家之前没有了解过动态规划,建议大家先去学习学习动态规划,直接开始01背包问题

    2024年04月15日
    浏览(49)
  • 动态规划:01背包问题(二)

    上篇博客动态规划:01背包问题(一)将的是用二维数组来解决,而本篇博客就是把二维dp数组降为一维dp数组(滚动数组)在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 其实可以发现如果 把dp[i - 1]那一层拷贝到dp[i]上 ,表达式完全可以是

    2024年01月22日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包