背包的转化

zrl123456 · 2024-03-30 11:15:32 · 题解

背包的转化

并不是所有的背包都那么明显，有时候需要进行转化。

例题 1：

例题 1

题目大意：

有 n 个物品，每个物品要么花费 A 代价 t_i 元，要么花费 B 代价 w_i 元，使最后的总代价 A 比 B 大，求最小的总代价 A。

数据范围：

• n\in[1,100]
• t_i\in\{1,2\}
• w_i\in[1,100]

  做法：

  我们可以设 f_{i,j,k} 为前 i 个物品，花费了 A 代价 j 元，B 代价 k 元的可行性，可行为 1，不可行为 0，边界条件为 f_{0,0,0}=1。
  推出转移方程：

  f_{i,j,k}=\begin{cases}1&j\ge t_i\land f_{i-1,j-t_i,k}\\1&k\ge w_i\land f_{i-1,j,k-w_i}\\0&otherwise\end{cases}

  最后倒序循环枚举 f_{n,i,j}，找到第一个可行的直接输出 i 即可。
  总体时空复杂度为 O(n(\sum t_i)^2)。
  代码：

  #include<bits/stdc++.h>
  #define int long long
  #define rep(i,x,y) for(int i=x;i<=y;++i)
  #define per(i,x,y) for(int i=x;i>=y;--i)
  #define repe(i,x,y,z) for(int i=x;i<=y;i+=z)
  #define eper(i,x,y,z) for(int i=x;i>=y;i-=z)
  #define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #define inl inline
  #define INF LLONG_MAX
  using namespace std;
  const int N=105,T=205;
  int n,t[N],w[N],sum;
  bool f[N][T][T];
  signed main(){
  fst;
  cin>>n;
  rep(i,1,n){
      cin>>t[i]>>w[i];
      sum+=t[i];
  }
  f[0][0][0]=1;
  rep(i,1,n)
      rep(j,0,sum)
          rep(k,0,sum){
              if(j>=t[i]) f[i][j][k]|=f[i-1][j-t[i]][k];
              if(k>=w[i]) f[i][j][k]|=f[i-1][j][k-w[i]];
          }
  rep(i,0,sum)
      rep(j,0,i)
          if(f[n][i][j]){
              cout<<i;
              return 0;
          }
  return 0;
  }