【洛谷】P1049装箱问题（01背包）

题目链接

题目描述

有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30，每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入输出格式

输入格式：

1个整数，表示箱子容量

1个整数，表示有n个物品

接下来n行，分别表示这n个物品的各自体积

输出格式：

1个整数，表示箱子剩余空间。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

箱子的剩余空间最小即要求所有挑选方案中体积和的最大值。01背包。

AC代码：

 1 #include<iostream>
 2 #include<sstream>
 3 #include<algorithm>
 4 #include<string>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<vector>
 8 #include<cmath>
 9 #include<ctime>
10 #include<stack>
11 #include<queue>
12 using namespace std;
13 int dp[31][20010];//dp[i][j]表示前i个物品在箱子容量为j时的最大体积和 
14 int main()
15 {
16     int V,n,v[31];
17     memset(dp,0,sizeof(dp));
18     cin>>V>>n;
19     for(int i=1;i<=n;i++) cin>>v[i];
20 
21     for(int i=1;i<=n;i++)
22     {
23         for(int j=0;j<=V;j++)
24         {
25             if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]);//第i个物品要么不选，要么选 
26             else dp[i][j]=dp[i-1][j];
27         }
28     }
29     
30     cout<<V-dp[n][V];
31 }

View Code

空间优化：（注意第二层循环是从右到左，完全背包是从左到右）

 1 #include<iostream>
 2 #include<sstream>
 3 #include<algorithm>
 4 #include<string>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<vector>
 8 #include<cmath>
 9 #include<ctime>
10 #include<stack>
11 #include<queue>
12 using namespace std;
13 int dp[20010];
14 int main()
15 {
16     int V,n,v[31];
17     memset(dp,0,sizeof(dp));
18     cin>>V>>n;
19     for(int i=1;i<=n;i++) cin>>v[i];
20 
21     for(int i=1;i<=n;i++)
22     {
23         for(int j=V;j>=v[i];j--)
24             dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
25     }
26     
27     cout<<V-dp[V];
28 }
29

View Code