这道题看似是搜索，但是可以用背包做。 题目要求求出最小的剩余空间，也就是要求出最大的可装重量 这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的 010101 背包问题： 有一个箱子容量为 VVV （正整数， 000 ＜＝ VVV ＜＝ 200002000020000 ），同时有 nnn 个物品（ 000 ＜ nnn ＜＝ 303030 ），每个物品有一 个体积（正整数）和一个价值（等于体积）。 要求 nnn 个物品中，任取若干个装入箱内，使总价值最大。 对于每一个物体，都有两种状态：装 与不装 那么，对于任意重量 mmm 的最大价值 fff ( mmm ) === maxmaxmax ( fff ( mmm −-− www [ iii ] ) +++ www [ iii ], fff ( mmm ) )（ www 为重量（即价值）） 其中， fff ( mmm −-− www [ iii ] ) 指在装了物品 iii 后，箱子的剩余容量能装的最大重量 fff ( mmm −-− www [ iii ] ) +++ www [ iii ] 指在在装了物品 iii 后，箱子能装的最大重量

洛谷里这个没有re的

#include<bits/stdc++.h> using namespace std; int n,m,w; int dp[20005]={0}; int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ scanf("%d",&w); for(int j=m;j>=w;j--){ if(j>=w){ dp[j]=max(dp[j],w+dp[j-w]); } } } printf("%d",m-dp[m]); return 0; }

逝十分简单的一道01背包的题 欢迎加入团队

题解： 问题分析 这是一个经典的01背包问题变形。我们要从 n 个物品中选择若干件放入容量为 V 的箱子，使得剩余空间最小。 关键转化： * 剩余空间最小 = 装入物品的总体积最大 * 装入物品总体积 ≤ 箱子容量 V * 目标：在不超过容量的前提下，尽可能多装物品 因此，问题转化为： 求在容量 V 限制下，能装入物品的最大总体积 解题思路 方法：动态规划（01背包） 定义 dp[j] 表示容量为 j 的箱子能装的最大物品总体积。 状态转移方程： 倒序枚举是为了确保每个物品最多被选择一次（01背包特点）。 算法步骤： 1. 输入箱子容量 V 和物品数量 n 2. 初始化 dp 数组为 0 3. 对于每个物品，更新 dp 数组 4. 最终答案为 V - dp[V] 时间复杂度：O(N×V) * n ≤ 30, V ≤ 20000，计算量约为 60 万次操作，完全可行 代码实现 样例解释 样例输入： 最优装法：8 + 3 + 7 + 6 = 24（刚好装满） 剩余空间 = 24 - 24 = 0 注意事项 1. 数组大小要开到 20000 以上 2. 内层循环必须倒序，保证每个物品只选一次 3. 初始条件 dp[0] = 0 表示空箱子容量为 0 时装的物品体积为 0 总结 本题是标准的01背包问题，通过动态规划可以高效求解。关键是理解“剩余空间最小”等价于“装入物品总体积最大”。

#include <bits/stdc++.h> using namespace std; int v,n,w,dp[20005]; int main(){ cin>>v>>n; for(int i=1;i<=n;i++){ cin>>w; for(int j=v;j>=w;j--) dp[j]=max(dp[j],w+dp[j-w]); } cout<<v-dp[v]; return 0; }

典型的背包问题，动归问题，原题在ybt

很正常的01背包，动态公式为 dp[j]=dp[j-w[i]]+w[i] 上代码——

#include<bits/stdc++.h> using namespace std; const int V=2e4+10; int main(){ int v,n,dp[35][V]={}; int w[105]={}; cin>>v>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=v;j++){ if(j>=w[i]){ dp[i][j]=max(dp[i-1][j],w[i]+dp[i-1][j-w[i]]); }else{ dp[i][j]=dp[i-1][j]; } } } cout<<v-dp[n][v]; return 0; }