[动态规划第一节]背包问题汇总

  • 背包问题

    • 动态规划思路:
      • 状态表示 f(i, j)

        • 状态由几维表示
          • 表示的集合是什么
            • 所有选法
            • 选法条件
              • 只考虑前i个物品
              • 总体积 <= j
          • 集合的属性是什么
            • 最大值
            • 最小值
            • 元素的数量
      • 状态计算

        • 集合的划分 f(i, j)
          • 不含第i个物品
            • f(i - 1, j)
          • 包含第i个物品
            • f(i - 1, j - vi) 已知第i个物品必选,那么只要保证前i-1个物品为最大值
    • 01背包

      • 每件物品最多取一次
      • 朴素代码:
        const int N = 1e3 + 10;
        int f[N][N], v[N], w[N];
        int n, m;
        
        int main(){
            cin >> n >> m;
            for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
            
            //f[1~n][0] = f[0][1~m] = 0;
            for(int i = 1; i <= n; ++ i) //遍历物品
                for(int j = 1; j <= m; ++ j){ //遍历容量
                    f[i][j] = f[i - 1][j]; //不选第i个物品
                    if(j >= v[i])
                        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //选第i个物品
                }
                
            cout << f[n][m];
            return 0;
        }
        
      • 优化:
        • 用滚动数组优化
        • 因为第i层总是由第i-1层来更新,不会用到1~i-2层,因此只用一维数组f[N]即可自我更新,f[j]表示不超过容量j的最大价值
        • 第i个物品不取,第i层与第i-1层的总价值不变,因此可以不用更新,\(f[i][j] = f[i - 1][j]\) 这句话可删去
        • 第i个物品取,因此要用i-1层更新第i层,\(f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])\) 并且总是用小容量的价值更新大容量的价值,若从小往大更新,那么小容量的价值优先被更新到第i层,大容量的价值依据小容量的价值更新时,使用的价值不再是第i-1层,所以容量要从大往小更新
        • 代码:
          const int N = 1e3 + 10;
          int f[N], v[N], w[N];
          int n, m;
          
          int main(){
              cin >> n >> m;
              for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
              
              //f[0] = 0;
              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]); //选第i个物品
                  
              cout << f[m];
              return 0;
          }
          
    • 完全背包

      • 每件物品可取无限次
      • 朴素代码:
        const int N = 1e3 + 10;
        int f[N][N], w[N], v[N];
        int n, m;
        
        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 = 1; j <= m; ++ j) //遍历容量
                    for(int k = 0; k * v[i] <= j; ++ k) //遍历个数 
                        f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                        
            cout << f[n][m];
            return 0;
        }
        
      • 时间优化:
        • \(f[i][j] = max(f[i - 1][j],f[i - 1][j - v] + w,f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,...,f[i-1][j-kv]+kw)\)
        • \(f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+w,...,f[i-1][j-kv]+(k-1)w,f[i-1][j-(k+1)v]+kw)\)
        • 发现: \(f[i][j]=max(f[i-1][j],f[i][j-v]+w)\)
        • 代码:
          const int N = 1e3 + 10;
          int f[N][N], w[N], v[N];
          int n, m;
          
          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 = 1; j <= m; ++ j){ //遍历容量
                      f[i][j] = f[i - 1][j]; //第i个物品不选
                      if(j >= v[i])
                          f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);//第i个物品选
                  }
                          
              cout << f[n][m];
              return 0;
          }
          
      • 时空优化:
        • 滚动数组优化
        • 代码:
          const int N = 1e3 + 10;
          int f[N], w[N], v[N];
          int n, m;
          
          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[j] = max(f[j], f[j - v[i]] + w[i]);
                          
              cout << f[m];
              return 0;
          }
          
    • 多重背包

      • 每件物品可取有限次
      • 朴素代码:
        const int N = 110;
        int f[N][N], v[N], w[N], s[N];
        int n, m;
        
        int main(){
            cin >> n >> m;
            for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
            
            for(int i = 1; i <= n; ++ i)
                for(int j = 1; j <= m; ++ j)
                    for(int k = 0; k <= s[i] && k * v[i] <= j; ++ k)
                        f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                        
            cout << f[n][m];
            return 0;
        }
        
      • 空间优化:
        • 滚动数组优化
        • 代码:
          const int N = 110;
          int f[N], v[N], w[N], s[N];
          int n, m;
          
          int main(){
              cin >> n >> m;
              for(int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
              
              for(int i = 1; i <= n; ++ i)
                  for(int j = m; j >= v[i]; -- j)
                      for(int k = 0; k <= s[i] && k * v[i] <= j; ++ k)
                          f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
                          
              cout << f[m];
              return 0;
          }
          
      • 二进制优化:
        • 将每个物品取的次数分为若干组,各组为1,2,4,8....2^k,c 的二进制数,在组中任意选取若干组,每组看作新的物品只能选一次,所有的次数都能由这几组二进制数表示,由于每组只能选一次,故化为01背包问题
        • 代码:
          const int N = 2e4 + 500;
          int v[N], w[N], s[N];
          int f[N];
          int n, m;
          
          int main(){
              cin >> n >> m;
              
              int cnt = 0; //记录物品个数
              while(n -- ){
                  int V, W, S;
                  cin >> V >> W >> S;
                  int k = 1; //记录分解后每个物品的次数
                  while(k <= S){ //将数量S分解
                      cnt ++ ; //每次分解个数加一
                      w[cnt] = W * k;
                      v[cnt] = V * k;
                      S -= k;
                      k *= 2;
                  }
                  if(S > 0){ //剩余次数
                      cnt ++ ;
                      w[cnt] = W * S;
                      v[cnt] = V * S;
                  }
              }
              
              n = cnt; //01背包问题
              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];
              return 0;
          }
          
    • 分组背包

      • 每个组里面最多选一件物品
      • 朴素代码:
        const int N = 110;
        int v[N][N], w[N][N];
        int f[N][N];
        int s[N];
        int n, m;
        
        int main(){
            cin >> n >> m;
            
            for(int i = 1; i <= n; ++ i){
                cin >> s[i];
                for(int j = 1; j <= s[i]; ++ j)
                    cin >> v[i][j] >> w[i][j];
            }
            
            for(int i = 1; i <= n; ++ i)
                for(int j = 1; j <= m; ++ j){
                    f[i][j] = f[i - 1][j]; //该组不选物品
                    for(int k = 1; k <= s[i]; ++ k){ //该组选物品
                        if(j >= v[i][k])
                            f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
                    }
                }
                
                        
            cout << f[n][m];
            return 0;
        }
        
        //或者
        for(int i = 1; i <= n; ++ i)
        	for(int k = 1; k <= s[i]; ++ k)
        		for(int j = 1; j <= m; ++ j){
        			f[i][j] = max(f[i][j], f[i - 1][j]);
        			if(j >= v[i][k])
        				f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        		}
        
        
      • 空间优化:
        const int N = 110;
        int v[N][N], w[N][N];
        int f[N];
        int s[N];
        int n, m;
        
        int main(){
            cin >> n >> m;
            
            for(int i = 1; i <= n; ++ i){
                cin >> s[i];
                for(int j = 1; j <= s[i]; ++ j)
                    cin >> v[i][j] >> w[i][j];
            }
            
            for(int i = 1; i <= n; ++ i)
                for(int j = m; j >= 1; -- j)
                    for(int k = 1; k <= s[i]; ++ k)
                        if(j >= v[i][k])
                            f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    
                        
            cout << f[m];
            return 0;
        }
        

热门相关:我的治愈系游戏   未来兽世:买来的媳妇,不生崽   大妆   本法官萌萌哒   本法官萌萌哒