首页 > 试题广场 >

最少数量货物装箱问题

[编程题]最少数量货物装箱问题
  • 热度指数：8900 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有重量分别为 3，5，7 公斤的三种货物，和一个载重量为 X 公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

数据范围：

输入描述:
输入箱子载重量(一个整数)。


输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。
示例1

输入

4

输出

-1

说明

无法装满
示例2

输入

8

输出

2

说明

使用1个5公斤，1个3公斤货物
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:59:04
精华题解 题目难度：二星 考察点：动态规划 方法1：暴力 1. 分析： 这道题类似于完全背包问题，每个货物都可以无限使用，但是要求背包必须装满，而且要求背包中的物品数目最少。由于货物是无限的，那么假设dp[n]表示背包容量为n的能够装满的最少货物个数，如果选择3, 5, 7任意的一种货物重量，那 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 猜猜我是谁⊙∀⊙！
发表于 2019-08-22 23:28:23
看了这么多解答，各种回溯法的确可以做，但没有写到点子上，就是一个背包问题的变种和lintcode 上的换硬币问题是一模一样的：https://www.lintcode.com/problem/coin-change/description if __name__ == "__main__": 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 白伟仝
发表于 2020-05-08 13:24:47
O(1)数论解法： import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 忧郁的小黑
发表于 2023-01-12 22:57:53
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 laglangyue
发表于 2020-05-26 22:21:14
当我看到这一题的时候，就感觉可以利用数学方法解决，只要枚举前面十几个数就就能求解；因为贪心，一直减7到14，以内就肯定直接得到解。最后用动态规划写出来，顺便复习一下动态规划，F(n)=F(n-7)+1 if:F(n-7)有解,F(n-5)+1 if:F(n-5)有解，F(n-3)+1 if:F(n- 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 右神
发表于 2022-08-15 15:48:02
这是一个背包问题 import java.util.*; public class Main{     public static void main(String[] args){ & 展开全文
去ta的博客 赞 (0) 回复(1) 收起

问题信息

C++工程师 贪心 动态规划 快手 2019 游戏研发工程师 Java工程师
上传者：小小
难度：
42条回答 9234浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号