装箱问题

[编程题]装箱问题

热度指数：6685 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

1个整数，表示箱子剩余空间。

示例1

输入

输出

算法知识视频讲解

savage

发表于 2019-08-20 16:00:11

题目描述有一个箱子容量为V（正整数，），同时有n个物品（），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述: 1个整数，表示箱子容量 1个整数，表示有n个物品接下来n行，分别表示这n个物品的各自展开全文

dass90

发表于 2022-12-26 17:20:37

Thinking Process 1、先确定状态 f[i][j]:前i个物体能不能装满体积为j的背包? 则现在有两个选择：选第i个物体：要看一下f[i-1][j-c[i]]，它能装下，那这个决定就可以装下不选第i个物体：要看一下f[i-1][j] 故推出状态方程： f[i][j] = f[i 展开全文

牛客338107602号

发表于 2022-07-10 20:12:00

总结：本题使用动态规划 import java.util.*; public class Main{ public static void main(String arg[]){ Scanner sc = new Scanner(System.in); int 展开全文

破竹GYH

发表于 2022-05-09 16:41:08

#include<bits/stdc++.h> using namespace std; int main() { int n; int v; cin >> v; cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积展开全文

狗都不学py算法

发表于 2022-01-27 00:16:06

解法： 01背包 dp 为什么可以用01背包来解？当我开始思考这道题的时候，首先排除的01背包，一方面感觉V太大，另一方面是存在一个误解：最后得出的最大值有可能超过箱子的容量。实则不然，当物品的价值等于物品的大小时，计算dp[i][j]的过程中，j（容量）一直限制dp[i][j]的大小，dp[i 展开全文

Gnomeshgh112

发表于 2025-04-09 15:55:12

0-1背包的变型dp[i][j]表示考虑了前i个物品，当背包大小为j的时候，剩余的最少空间。初始化：起初一个物品都没有放入，所以dp[0][j] = j；转移方程：if (a[i] < j) dp[i][j] = min(dp[i - 1][j], dp[j - a[i]]);else dp[ 展开全文