动态规划模板总结(1)

动态规划思想(1)

---

背包问题

​ 分类：

---

01 背包问题

​

• 含义：每个物体最多选1次，在不超过总体积的情况下价值最大
• 图解：

• f(i,j)表示的是集合的某种属性，是个值。

• 集合是所有选法

• i 只从前i个中选

• 朴素实现

  #include
  #include
  
  using namespace std;
  
  const int N = 1010;
  
  int n,m;//n代表物品个数m代表容量
  int v[N],w[M];//v代表体积，w代表价值
  int f[N][N];//全局变量默认为0
  
  int mian(){
  	cin >> n >> m;
  	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
  	//for[0][0~m]//考虑0件物品，最大价值不超过0~m  但默认为0所以可以不写
  	for(int i = 1; i <= n; i++)
  		for（int j = 0; j <= m; j++）{//j代表体积
  			f[i][j] = f[i-1][j]//代表左边不含i的情况
  			if(j >= v[i])//如果第i件物品体积大于背包就装不下了
  				f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
  		}
  		
  		cout << f[n][m] << endl;
  		
  		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

  • 一维实现

    
    #include
    #include
    
    using namespace std;
    
    const int N = 1010;
    
    int n,m;//n代表物品个数m代表容量
    int v[N],w[M];//v代表体积，w代表价值
    int f[N];//全局变量默认为0
    
    int main(){
        	cin >> n >> m;
        
        for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
        
        for(int i = 1;i <= n; i++)
            for(int j = m; j >= v[i];j--)
                f[j] = max(f[j],f[j-v[i]] + w[i]);
        cout << f[m] << endl;
        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

• 滚动数组：如果f()只用到了上层的数据，完全可以只用f(2)和f(1)交替来算。不需要创建额外的空间。

• 一维实现：运用了滚动数组的思想，每次找最大值就是从前面一次的数组寻值，而且由于公式的原因不可能从原地址取值。运用了一维就可以直接把前面i代表的那一维去掉

---

02完全背包问题

• 朴素实现

  #include
  #include
  
  using namespace std;
  
  const int N = 1010;
  
  int n,m;
  int v[N],W[N];
  int f[N][N];
  
  int main(){
  	cin >> n >> m;
  	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
      
      for(int i =1;i <= n; i++)
          for(int j = 0; j <= m; j++)
              for(int k = 0; k*v[i] <= j;k++)
                  f[i][j] = max(f[i][j],f[i-1][j - v[i]*k] + w[i] * k);
      
      cout << f[n][m] << endl;
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

  优化思路：

• 代码

  #include
  #include
  
  using namespace std;
  
  const int N = 1010;
  
  int n,m;
  int v[N],W[N];
  int f[N][N];
  
  int main(){
  	cin >> n >> m;
  	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
      
      for(int i =1;i <= n; i++)
          for(int j = 0; j <= m; j++)
          {
              f[i][j] = f[i-1][j];
              if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]] + w[i])//
          }
      cout << f[n][m] << endl;
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 和01背包问题比较，可以看出还能继续优化

#include
#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],W[N];
int f[N];

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i =1;i <= n; i++)
        for(int j = v[i]; j <= m; j++)
       f[i][j] = max(f[j],f[j-v[i]] + w[i]);
    cout << f[m] << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

; i <= n; i++) cin >> v[i] >> w[i];

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

}

- 01背包问题从小到大，完全背包是从大到小。为什么01和完全只差个顺序呢？
1
2