面试题：有一个箱子容积为v，同时有n个物品，每个物品有一个体积。要求从n个物品中,任取若干个装入箱内，使箱子的剩余空间最小。

面试题

有一个箱子容积为v，同时有n个物品，每个物品有一个体积。要求从n个物品中,任取若干个装入箱内，使箱子的剩余空间最小。

输入

箱子的容积 v
物品个数 n
每个物品占的空间 x1,x2…xn

输出

最小剩余空间 s

解题思路

背包类动态规划问题，假设若当前背包现容纳体积为j，此时若将物品i放入到背包中则容器中容纳状态为dp[j-n[i]] + n[i]，其中dp[j-n[i]]代表背包放置物品i之前的容量，n[i]就代表x1~xn中的某一个物品所占的空间，若该物品i未放入背包中，则容量状态不变为dp[j]，由此可得出动态转移方程 dp[j] = max(dp[j],dp[j-n[i]] + n[i])，在此过程中需要遍历每一个物品找到最优解

• 以下代码在最新C++规则中不支持，数组大小必须定义为常量，可通过指针类型new开辟数组，使用指针进行操作

题解

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vld.h>
using namespace std;
int main()
{
	int v,n;
	cout << "请输入体积：";
	cin >> v;
	cout << "请输入物品个数:";
	cin >> n;
	int box[n] = {};
	cout << "初始化物品体积：";
	for(int i = 0;i<n;i++)
	{
		cin >> box[i];
	}
	int dp[v+1] = {0};//表示容积为v时可放置物品的容量
	for(int i = 0;i < n; i++)
	{
		for(int j = v ;j > box[i]; j--)
		{
			dp[j] = max(dp[j],dp[j-box[i]] + box[i])
		}
	}
	cout<<v-dp[v];
	system("pause");
	return 0;
}