背包问题找物品

艾迪是参加ACM ICPC比赛的选手。ACM是算法、编码和数学的简称。因为在ACM比赛中，最重要的知识是算法，其次是编码(实现能力)，然后是数学。然而，在2018年ACM ICPC世界总决赛上，艾迪没能解出一个物理方程，这让他失去了一枚可能的奖牌。
从那时起，艾迪发现物理学实际上是竞赛中最重要的东西。因此，他想组建一个团队来指导接下来的选手去征服PACM比赛(PACM是物理、算法、编码、数学的简称)。
有N个候选组，每个组由pi物理专家、ai算法专家、ci编码专家、mi数学专家组成。对于每一组，艾迪可以邀请所有的人，也可以不邀请他们。如果i-th团队被邀请，他们将带来gi知识点，这是由Eddy的神奇公式计算出来的。艾迪认为，一个团队的总知识点越高，就越能在比赛中占据优势。但是，艾迪不希望邀请的团体中有太多在同一领域的专家。因此，邀请物理专家的数量不应超过P，算法专家A，编码专家C，数学专家M。
艾迪仍在忙于学习物理学。你来帮助他弄清楚应该邀请哪些组，这样他们就不会超出限制，并将带来最多的知识点。

这个是多维的01背包代码

#include<bits/stdc++.h>
#define MAX 40
using namespace std;
int dp[MAX][MAX][MAX][MAX];
bool book[MAX][MAX][MAX][MAX][MAX];
int a[MAX],b[MAX],c[MAX],d[MAX],v[MAX];
int ans[MAX];
int A,B,C,D;
int main(void){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d %d %d",&a[i],&b[i],&c[i],&d[i],&v[i]);
    }
    scanf("%d %d %d %d",&A,&B,&C,&D);
    for(int i=0;i<n;i++)
        for(int k1=A;k1>=a[i];k1--)
            for(int k2=B;k2>=b[i];k2--)
               for(int k3=C;k3>=c[i];k3--)
                 for(int k4=D;k4>=d[i];k4--)
        {
            if(dp[k1-a[i]][k2-b[i]][k3-c[i]][k4-d[i]]+v[i]>dp[k1][k2][k3][k4])
            {
                dp[k1][k2][k3][k4]=dp[k1-a[i]][k2-b[i]][k3-c[i]][k4-d[i]]+v[i];
            book[i][k1][k2][k3][k4]=1;
            }
        }
    int k=0;
    for(int i=n-1;i>-1;i--){
        if(book[i][A][B][C][D])
        {
            ans[++k]=i;
            A-=a[i];
            B-=b[i];
            C-=c[i];
            D-=d[i];
        }
    }
    printf("%d
",k);
    for(int i=k;i>0;i--)
        printf("%d
",ans[i]);
}

这个是多重背包

#include<bits/stdc++.h>
#define MAX 1000005
#define INF 0x3f3f3f3f
using namespace std;
int dp[MAX];
int sing[MAX];
int main(void){
 int n;
 memset(sing,-1,sizeof(sing));
 scanf("%d",&n);
 int minm=INF;
 int a[10];
 int it=-1;
 for(int i=1;i<=9;i++){
    scanf("%d",&a[i]);
    if(a[i]<minm)
        minm=a[i];
    }
    if(n<minm){
        printf("-1
");
        return 0;
    }
    for(int i=9;i>=1;i--)
       for(int j=a[i];j<=n;j++){
       int temp=dp[j-a[i]]+1;
       if(temp>dp[j]){
        dp[j]=temp;
        sing[j]=i;//记录物品；
       }
    }
    int j=n;
    map<int,int>mp;
    while(sing[j]!=-1){//遍历物品。
        mp[sing[j]]++;
        j-=a[sing[j]];
    }
    for(int i=9;i>=1;i--){
        if(mp[i]!=0){
            for(int j=0;j<mp[i];j++){
                printf("%d",i);
            }
        }
    }
    return 0;
}