装箱问题（信息学奥赛一本通-1917/1295）

【题目描述】

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

【输入】

第一行是箱子的容量,第二行是n(表示n有n个物品),接下来n行是n个物品的体积。

【输出】

最小空间

【输入样例】

24
6
8
3
12
7
9
7

【输出样例】

0

【题解代码】

#include<bits/stdc++.h>
using namespace std;int v;  //箱子容量
int n;  //物品个数
int nv[35];  //每个物品的体积
bool vis[35];  //标记数组
int cnt[10];  //每层元素
int minx = 0x3f3f3f3f;  //最小剩余空间，初始值应设置为最大//在第depth阶段搜索目标体积s  
void dfs(int start, int s, int depth)
{//注意这三条语句的顺序if (s > v) return;minx = min(minx, v - s);if (depth > n) return;// 1、枚举方案for (int i = start; i <= n; i++) {//2、查看是否被标记-防止重复搜索if (!vis[i])  {//3、搜索cnt[depth] = nv[i];  //4、标记vis[i] = 1;//5、搜索下一层dfs(i + 1, s + nv[i], depth + 1);//6、回溯vis[i] = 0;}}return;
}int main()
{cin >> v >> n;for (int i = 1; i <= n; i++){cin >> nv[i];}dfs(1, 0, 1);cout << minx;return 0;
}