二刷提高课,题解目录在这里— 提高课的题解目录
使得箱子剩余空间最小,也就是所选空间最大
所以我们可以将所占的体积看成价值,其实就是个01背包问题
在给定容量内选取的体积最大,因为题目要求剩余体积所以减去即可
#include<iostream>
using namespace std;
int f[40][20010],v[40];
int main(){
int n,w;
cin>>w;
cin>>n;
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=w;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]);
}
cout<<w-f[n][w];
}