题目描述
有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。
要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
算法:01背包
时间复杂度:O(N*M)
需要注意
(1)这里的价值体积都是题干中的体积
(2)求的是剩余的体积的最小值,需要在输出的时候用总体积减去已经装满的体积
C++代码
#include<iostream>
using namespace std;
const int N=35,M=20010;
int f[M];
int v[N];
int n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+v[i]);
cout<<m-f[m]<<endl;
return 0;
}