作者：henu-菜鸡三人行
链接：https://www.nowcoder.com/discuss/88433?type=101&order=0&pos=1&page=0
来源：牛客网

题意按照我的理解就是相当于一个具有多个重量W的01背包。就是从一个W扩展到P,A,C,M四个属性。
大概做法就是按照01背包的样式进行改写就可以了，因为范围很小只有36,所以时间复杂度就是个五层的循环，大概O(pow(36,5)) = 6000w左右，不会超时，这里要降一层数组，就是4层的一个dp数组就够了。也不会超内存.使用记录路径的方法，直到最后再还原回去把加入的物品记录下来最后再输出。也就是一个很裸的做法。

四重背包并输出路径

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 38;
int dp[N][N][N][N];
bool path[N][N][N][N][N];
int a[N],b[N],c[N],d[N],v[N];
int main()
{
    memset(dp,0,sizeof dp);
    memset(path,0,sizeof path);
    int nn;
    cin>>nn;
    for(int i=0;i<nn;i++)
    {
        scanf("%d%d%d%d%d",&a[i],&b[i],&c[i],&d[i],&v[i]);
    }
    int A,B,C,D;
    cin>>A>>B>>C>>D;
    for(int i=0;i<nn;i++)
    {
        for(int j=A;j>=a[i];j--)
        {
           for(int k=B;k>=b[i];k--)
           {
               for(int m=C;m>=c[i];m--)
               {
                   for(int n=D;n>=d[i];n--)
                   {
                      if(dp[j][k][m][n]<dp[j-a[i]][k-b[i]][m-c[i]][n-d[i]]+v[i])
                      {
                          dp[j][k][m][n]=dp[j-a[i]][k-b[i]][m-c[i]][n-d[i]]+v[i];
                          path[i][j][k][m][n] = 1;
                      }
                   }

               }
           }
        }
    }
    vector<int>ans;
    int j=A,k=B,m = C,n = D;
    for(int i=nn-1;i>=0&&j>=0&&k>=0&&m>=0&&n>=0;i--)
    {
        if(path[i][j][k][m][n])
        {
             ans.push_back(i);
        j-=a[i];
        k-=b[i];
        m-=c[i];
        n-=d[i];
        }

    }
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto p:ans)
    {
        cout<<p<<endl;
    }

    return 0;
}