洛谷P1049 装箱问题

题目描述

有一个箱子容量为V（正整数，0 \le V \le 200000≤V≤20000），同时有n个物品（0<n \le 300<n≤30，每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入输出格式

输入格式：

 

11个整数，表示箱子容量

11个整数，表示有nn个物品

接下来nn行，分别表示这nn个物品的各自体积

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 复制

24
6
8
3
12
7
9
7

输出样例#1： 复制

0

---

暴力搜索，深搜：对于地i个物体可以选择拿或者不拿：

#include<bits/stdc++.h>
using namespace std;
int vol,n,a[35],ans=0x3f3f3f;
//剩下的体积，第几个物体 
void search(int rest,int i)
{
	ans=min(ans,rest);
	if(i==n) return;
	if(rest-a[i]>=0)
	search(rest-a[i],i+1);//装进去，前提是能装的进去 
	search(rest,i+1);//不装 
}
int main()
{
	cin>>vol;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	search(vol,0);
	cout<<ans;
	return 0;
}