基于动态规划的0-1背包问题学习

关于动态规划

动态规划是一种解决多阶段决策过程最优化问题的数学方法。其基本思想是将问题分解成若干个子问题，通过求解子问题的最优解来推导出原问题的最优解。

具体而言，动态规划方法可以分为两个步骤：

定义状态：将原问题转化为某一阶段的子问题，并记录下该子问题的最优解。

状态转移方程：通过对每个子问题的最优解进行组合，得到原问题的最优解。

在定义状态时，需要明确每个状态所代表的含义和与其他状态之间的关系；在构造状态转移方程时，需要根据前一个状态推出当前状态，从而不断递推到最终状态，得到最优解。

动态规划方法通常适用于具有“无后效性”、“最优子结构”和“重复子问题”的问题，因为这些问题可以被分解为若干个子问题，在每个子问题中使用相同的状态转移方程，从而获得全局最优解。同时，动态规划方法也可以通过记忆化搜索的方式实现，避免了重复计算子问题。因此，它在解决大规模的各种优化问题上具有广泛的应用价值。

0-1背包问题

背景

给定指定体积的背包,商品的体积和价值,商品不能切割单位化。每个商品要么选择装入背包,要么不装入.

思想

用二维数组f[i][j]来表示背包在决策前i个商品时，容量为j时的价值.
背包容量按升序遍历,f[i-1][j]理解为保存在不同容量下对前i-1个物体的决策的最优解(最大价值).
状态转移方程: f[i][j] =max(f[i-1][j],f[i-1][j-v[i]]+w[i]);

初始状态

当背包容量为0时,背包的价值为0.

解决方案

二维数组的方式

  #include "iostream"
   using namespace std;

 

   const int  MAXNUM = 1e3+10;


   int goods[MAXNUM][MAXNUM];
   int VS[MAXNUM];
   int WEX[MAXNUM];
   int main()
   {
       
       int N ,V;
       cin>>N>>V;
       for(int i = 1;i<=N ; i++)
       {
           int v,w;
           cin>>v>>w;
           VS[i]=v;
           WEX[i]=w;
           
       }
       
       for(int i = 1; i <= N ;i++)
       {
           for(int j = 1 ; j<=V;j++)
           {
               
               if(VS[i] > j)
               {
                   goods[i][j] = goods[i-1][j]; //不装
               }
               else
               {
                   goods[i][j]= max(goods[i-1][j],goods[i-1][j-VS[i]]+WEX[i]);//装
                   
               }
           }
       }
           cout<<goods[N][V];
       
       
       
   
   return 0;   
   }
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

一维优化逆序容量遍历+输入优化

    #include "iostream"
    using namespace std;

    #define MAXNUM 1000+10


    int f[MAXNUM];
    
    int main()
    {
        
        int N ,V;
        cin>>N>>V;
        for(int i = 1;i<=N ; i++)
        {
            int v,w;
            cin>>v>>w;
            
            for(int  j = V; j >= v;j--)
            {
                f[j] = max(f[j],f[j-v]+w);
            }
            
        }
        
    cout<<f[V];
        
        
    
    return 0;   
    }
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
26
27
28
29
30
31

关于为什么要容量逆序原因:

若使用正序遍历则在决策第i个物体时,比如计算f[7]需要用到f[4],而因为容量是按照正序进行遍历,可能f[4]已经被计算过了,这样在算f[7]时可能会被影响(比如多算了1次被决策的物体的价值)
简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。
为了加深理解,模拟过程:

    n=4 m=5//物品个数为4，背包总体积为5

    v[1]=1,w[1]=5;
    v[2]=2,w[2]=4
    v[3]=3,w[3]=4
    v[4]=4,w[4]=5

    for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
    if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);

    01背包,逆序排列
    //依次判断每个物品
    //初始化全局定义f[N]=0
    i=1 j=5 此时j>=v[1]  f[5]=max(f[5],f[5-v[1]]+w[1])=max(f[5],f[4]+5)=5;//1
    i=1 j=4 此时j>=v[1]  f[4]=max(f[4],f[4-v[1]]+w[1])=max(f[4],f[3]+5)=5;//1
    i=1 j=3 此时j>=v[1]  f[3]=max(f[3],f[3-v[1]]+w[1])=max(f[3],f[2]+5)=5;//1
    i=1 j=2 此时j>=v[1]  f[2]=max(f[2],f[2-v[1]]+w[1])=max(f[2],f[1]+5)=5;//1
    i=1 j=1 此时j>=v[1]  f[1]=max(f[1],f[1-v[1]]+w[1])=max(f[1],5)=5;//1

    i=2,j=5 此时j>=v[2]  f[5]=max(f[5],f[5-v[2]]+v[2])=max(f[5],f[3]+4)=max(5,5+4)=9 //1 2
    i=2,j=4 此时j>=v[2]  f[4]=max(f[4],f[4-v[2]]+v[2])=max(f[4],f[2]+4)=max(5,5+4)=9 //1 2
    i=2,j=3 此时j>=v[2]  f[3]=max(f[3],f[3-v[2]]+v[2])=max(f[3],f[1]+4)=max(5,5+4)=9 //1 2
    i=2,j=2 此时j>=v[2]  f[2]=max(f[2],f[2-v[2]]+v[2])=max(f[2],f[0]+4)=max(5,4)=5 // 1

    i=3,j=5 此时j>=v[3] f[5]=max(f[5],f[5-v[3]]+v[3])=max(f[5],f[2]+4)=max(9,5+4)=9 //1+2 1+3
    i=3,j=4 此时j>=v[3] f[4]=max(f[4],f[4-v[3]]+v[3])=max(f[4],f[1]+4)=max(9,5+4)=9 //1+2 1+3
    i=3,j=3 此时j>=v[3] f[3]=max(f[3],f[3-v[3]]+v[3])=max(f[3],f[0]+4)=max(9,4)=9 //1+2
    ………//后续省略

    完全背包，正序排列

    n=4 m=5//物品个数为4，背包总体积为5
    v[1]=1,w[1]=5;
    v[2]=2,w[2]=4
    v[3]=3,w[3]=4
    v[4]=4,w[4]=5

    for (int i = 1; i <= n; i ++ )
            for (int j = v[i]; j <= m; j ++ )
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    //判断第一个物体 这里的正序决策前面数据被影响
    i=1 j=1 此时j<m f[1]=max(f[1],f[j-v[1]]+w[1])=max(f[1],f[1-1]+5)=max(0,5)=5//1//一个1
    i=1 j=2 此时j<m f[2]=max(f[2],f[j-v[1]]+w[1])=max(f[2],f[2-1]+5)=max(0,5+5)=10//两个1
    i=1 j=3 此时j<m f[3]=max(f[3],f[j-v[1]]+w[1])=max(f[3],f[3-1]+5)=max(0,10+5)=15//三个1
    i=1 j=4 此时j<m f[4]=max(f[4],f[j-v[1]]+w[1])=max(f[4],f[4-1]+5)=max(0,15+5)=20//四个1
    i=1 j=5 此时j=m f[5]=max(f[5],f[j-v[1]]+w[1])=max(f[5],f[5-1]+5)=max(0,20+5)=25//五个1

    i=2 j=2 此时j<m f[2]=max(f[2],f[j-v[2]]+w[2]=max(f[2],f[2-1]+4)=max(10,5+4)=10//两个1
    i=2 j=3 此时j<m f[3]=max(f[3],f[j-v[2]]+w[2]=max(f[3],f[3-1]+4)=max(15,10+4)=15//三个1
    i=2 j=4 此时j<m f[4]=max(f[4],f[j-v[2]]+w[2]=max(f[4],f[4-1]+4)=max(20,15+4)=20//四个1
    i=2 j=5 此时j<m f[5]=max(f[5],f[j-v[2]]+w[2]=max(f[5],f[5-1]+4)=max(25,20+4)=25//五个1
    ………//后续省略
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54