题解 P1049 【装箱问题】

我做这道题的第一反应:嗯?背包……

然后就没了…………

思路是把它当做重量和价值相同的物体放入背包

用背包公式可求最大能装多少, 剩余容积=V-最大装多少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>//P1049
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
using namespace std;
int a[20003];
int main()
{
int n,m,i,j,k;
cin>>m>>n;
for(i=1;i<=n;i++)
{
cin>>k;//边输边做程序比较简练
for(j=m;j>=k;j--)a[j]=max(a[j],a[j-k]+k);
}
cout<<m-a[m];//剩余容积
return 0;
}