分析背包的三要素

zrl123456 · 2024-03-29 16:06:27 · 题解

分析背包的三要素

背包的三要素分别是：物品，体积和价值。

例题

例题 1

题目大意：

• W\in[1,10^5]
• w_i\in[1,W]
• v_i\in[1,10^9]

  做法：

  这道题就是一个 01 背包的板子。
  我们就设 f_{i,j} 为前 i 个物品装入容量为 j 的背包里，所能获取的最大价值。
  易得状态转移方程：

  f_{i,j}=\max(f_{i-1,j-w_i}+v_i,f_{i-1,j})

  由于数据范围过小，不需要使用滚动数组即可通过。
  代码：

  #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,W=1e5+5;
  int n,w,ww[N],v[N],f[N][W];
  signed main(){
  fst;
  cin>>n>>w;
  rep(i,1,n) cin>>ww[i]>>v[i];
  rep(i,1,n){
      rep(j,0,ww[i]-1) f[i][j]=f[i-1][j];
      rep(j,ww[i],w) f[i][j]=max(f[i-1][j-ww[i]]+v[i],f[i-1][j]);
  }
  cout<<f[n][w];
  return 0;
  }

  例题 2

  题目大意：

  ### 数据范围：
• N\in[1,100]
• W\in[1,10^9]
• w_i\in[1,W]
• v_i\in[1,10^3]

  TLE/MLE 做法：

  参照上述做法，O(NW) 暴力做法，但会 TLE/MLE。

  正解：

  注意到 v_i 较小，我们可以尝试让 v_i 当背包和物品的体积，w_i 当价值。
  我们设 f_{i,j} 为前 i 个物品的体积为 j，使最后的价值最小。
  得状态转移方程：

  f_{i,j}=\min(f_{i-1,j-v_i}+w_i,f_{i-1,j})

  最后直接倒序循环查找，找到第一个 f_{n,j}\le w 的，直接输出即可。
  代码：

  #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,W=1e5+5;
  int n,w,ww[N],v[N],f[N][W],sum;
  signed main(){
  fst;
  cin>>n>>w;
  memset(f,0x3f,sizeof(f));
  rep(i,1,n){
      cin>>ww[i]>>v[i];
      sum+=v[i];
  }
  f[0][0]=0;
  rep(i,1,n){
      rep(j,0,v[i]-1) f[i][j]=f[i-1][j];
      rep(j,v[i],sum) f[i][j]=min(f[i-1][j-v[i]]+ww[i],f[i-1][j]);
  }
  per(i,sum,0)
      if(f[n][i]<=w){
          cout<<i;
          return 0; 
      }
  return 0;
  }