嗨害嗨 眼熟叶桁桉/殷淮葵 菜鸽咕咕咕。

首先 大部分人看到本题的第一思路就是贪心。即每次选择体积最大的装入箱中。

但是，贪心存在这样一个问题：局部最优解不一定是全局最优解。

当然贪心如果乱搞能过 这句话的添加来自弱谷某大佬的神仙做法。 链接附上：https://www.luogu.com.cn/blog/lhc123456/solution-p1049

菜鸽表示一脸震惊。但是看不懂也学不会。

因此，需要用动态规划解决此题

当总容量为 j 时，不放第 i 件物品，所能装的最大体积为f[j]。

当总容量为 j 时，放了第 i 件物品后，所能装的最大体积为f[j-w[i]]+w[i]。w[i] 为第 i 件物品体积

每个物体，都有装与不装两种选择。

所以我们可以得到得到状态转移方程。

f[j]=max(f[j],f[j-w[i]]+w[i]);

得到状态转移方程后 就可以完美的写出AC代码了

贴代码

#include <bits/stdc++.h>
using namespace std;
const int N=20010;
int V,n;
int v[N],f[N];

int main()
{
	cin>>V>>n; 
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=V;j>=v[i];j--)
		{
			if(j>=v[i])
			{
				f[j]= max(f[j],f[j-v[i]]+v[i]);		
			}
		}
	}
	cout<<V-f[V]<<endl;
	return 0;
}

好啦本题的题解就到这里。

上文所提洛谷大佬的题解如果有dalao学会。

可不可以教教菜鸽！（对手指）（对手指）

end.