DP(二装箱问题

题目描述
有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

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

输入格式
第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式
一个整数，表示箱子剩余空间。

数据范围
0<V≤20000,
0<n≤30

1.  
   样例
2.  
   输入样例：
3.  
   24
4.  
   6
5.  
   8
6.  
   3
7.  
   12
8.  
   7
9.  
   9
10.  
    7
11.  
    输出样例：
12.  
    0

思路一：DP
那么显而易见我们要让物品的体积尽量大，所以体积就是价值。
但是我们选一个物品，首先我们收获了价值，但箱子的体积也相应的减少了容量，所以体积还是价值。
意味着我们在让箱子剩余体积减少时，还能装的容量减少了（怎么这么不通顺）。
那就是01背包了。
只不过这里体积也是价值

时间复杂度 O(n*m)
参考文献
C 代码

1.  
   #include <iostream>
2.  
    
3.  
   using namespace std;
4.  
    
5.  
   const int N = 40, M = 10010;
6.  
   int n, m;
7.  
   int a[N];
8.  
   int f[N][M * 2];
9.  
   //f[i][j]表示考虑前i个物品，总体积不超过j的最大体积。
10.  
    int main() {
11.  
    cin >> m >> n;
12.  
    for (int i = 1; i <= n; i ) cin >> a[i];
13.  
     
14.  
    for (int i = 1; i <= n; i ) {
15.  
    for (int j = 1; j <= m; j ) {
16.  
    f[i][j] = f[i - 1][j];
17.  
    //不选当前物品
18.  
    if (j >= a[i]) f[i][j] = max(f[i][j], f[i - 1][j - a[i]] a[i]);
19.  
    //选当前物品，但体积必须足够
20.  
    }
21.  
    }
22.  
    cout << m - f[n][m] << endl; //注意是剩余体积
23.  
    return 0;
24.  
    }
25.  
     
26.  
    //优化
27.  
    #include <iostream>
28.  
    #include <cstring>
29.  
    #include <algorithm>
30.  
    using namespace std;
31.  
    const int N = 1e5 10;
32.  
    int f[N];
33.  
    int n,m;
34.  
    int main()
35.  
    {
36.  
    cin>>m>>n;
37.  
    memset(f,0,sizeof f);
38.  
    for (int i = 0; i < n; i )
39.  
    {
40.  
    int v;
41.  
    cin>>v;
42.  
    for (int j = m; j>=v; j -- )
43.  
    f[j]=max(f[j],f[j-v] v);
44.  
    }
45.  
    return cout<<m-f[m],0;
46.  
    }

Java代码

1.  
   import java.util.*;
2.  
   import java.io.*;
3.  
   public class Main{
4.  
   static int m,n;
5.  
   static int f[]=new int [100010];
6.  
   public static void main(String[] args){
7.  
   Scanner cin = new Scanner(System.in);
8.  
   m=cin.nextInt();
9.  
   n=cin.nextInt();
10.  
    for(int i=0;i<n;i )
11.  
    {
12.  
    int a=cin.nextInt();
13.  
    for(int j=m;j>=a;j--)
14.  
    f[j]=Math.max(f[j],f[j-a] a);
15.  
    }
16.  
    System.out.println(m-f[m]);
17.  
    return ;
18.  
    }
19.  
    }

思路二：逆序求最大容量
01背包f[j]表示容量为j的背包最多能装多少价值的物品
而下面的f[j]表示容量为j的背包是否能被装满
能想到这个也是非常nb的

时间复杂度 O(n*m)
参考文献
C 代码

1.  
   #include <iostream>
2.  
   #include <cstring>
3.  
   #include <algorithm>
4.  
   using namespace std;
5.  
   const int N = 1e5 10;
6.  
   int m,n;
7.  
   int f[N];
8.  
   int main()
9.  
   {
10.  
    cin>>m>>n;
11.  
    f[0]=1;
12.  
    for (int i = 0; i < n; i )
13.  
    {
14.  
    int v;
15.  
    cin>>v;
16.  
    for (int j = m; j >=v; j --)
17.  
    f[j]|=f[j-v];
18.  
    }
19.  
    for (int j = m; j; j --)
20.  
    if(f[j])
21.  
    return cout<<m-j,0;
22.  
    return 0;
23.  
    }

Java代码

1.  
   import java.util.*;
2.  
   import java.io.*;
3.  
   public class Main{
4.  
   static int m,n;
5.  
   static int f[]=new int [100010];
6.  
   public static void main(String[] args){
7.  
   Scanner cin = new Scanner(System.in);
8.  
   m=cin.nextInt();
9.  
   n=cin.nextInt();
10.  
    f[0]=1;
11.  
    for(int i=0;i<n;i )
12.  
    {
13.  
    int a=cin.nextInt();
14.  
    for(int j=m;j>=a;j--)
15.  
    f[j]|=f[j-a];
16.  
    }
17.  
    for (int j = m; j>=0; j --)
18.  
    if(f[j]==1)
19.  
    {
20.  
    System.out.println(m-j);
21.  
    return ;
22.  
    }
23.  
    return ;
24.  
    }
25.  
    }

欢迎留言点赞

嗷嗷嗷~

这篇好文章是转载于：学新通技术网