算法提高之金明的预算方案

核心思想：有依赖的背包dp + 分组背包
- 状态表示f[i,j]: 考虑前i个组，总体积不超过j的方案
- 状态计算：f(i,j)=max(f(i−1,j),f(i−1,j−vk+wk))
  - 遍历每种取附件的方案

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  #include <vector>
  
  using namespace std;
  const int N = 65 , M = 32010;
  bool is_aff[N];
  int f[M],v[N],w[N];
  vector<int> aff[N];
  int n,m;
  
  void dp(int u,int j)
  {
      int siz = aff[u].size();  //取附件个数
      for(int st=0;st<1<<siz;st++)  //二进制遍历每一种取附件的情况
      {
          int v_sum = v[u];  //取附件之前先取主件
          int w_sum = w[u];
          for(int i=0;i<siz;i++)  //遍历图中每一位 看看是不是取了
          {
              if(st>>i & 1)
              {
                  v_sum += v[aff[u][i]];
                  w_sum += w[aff[u][i]];
              }
          }
          if(j>=v_sum) f[j] = max(f[j],f[j-v_sum] + w_sum);  //取完所有附件 当前组的花费和价值
      }
  }
  int main()
  {
      cin>>m>>n;
      for(int i=1;i<=n;i++)
      {
          int fa;
          cin>>v[i]>>w[i]>>fa;
          w[i] *= v[i];
          if(fa) aff[fa].push_back(i);  //分组存入编号为fa的组
          else is_aff[i] = true;  //标记编号为i的物品为主件
      }
  
      for(int i=1;i<=n;i++)
          if(is_aff[i])  //如果是主件
              for(int j=m;j>=0;j--)  //做01背包
                  dp(i,j);
  
      cout<<f[m]<<endl;
      return 0;
  }