分组背包 二进制遍历每个组中的每个策略

java版本

import java.util.*;
public class Main{
    static int N=62,M=32010;
    static int[] f=new int[M];
    static int n,m;
    static int o=0;
    static List<int[]>[] servent;
    static int[][] master;
    public static void main(String [] rags){
        Scanner sc=new Scanner(System.in);
        m=sc.nextInt();
        n=sc.nextInt();
        master=new int[n+1][2];
        servent=new ArrayList[n+1];
        for(int i=0;i<=n;i++) servent[i]=new ArrayList<>();//和c++不同，java如果不初始化就会被自动初始化为null的
        for(int i=1;i<=n;i++){
            int v,p,q;
            v=sc.nextInt();
            p=sc.nextInt();
            q=sc.nextInt();
            p=p*v;
            if(q==0) master[i]=new int[]{v,p};//master[i]={v,p}这种写法只能在初始化用
            else servent[q].add(new int[]{v,p});
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--){
                //遍历每个情况
                for(int k=0;k<1<<servent[i].size();k++){
                    int v=master[i][0],w=master[i][1];
                    for(int h=0;h<servent[i].size();h++){
                        if((k>>h&1)==1){
                            v+=servent[i].get(h)[0];
                            w+=servent[i].get(h)[1];
                        }
                    }
                    if(j>=v) f[j]=Math.max(f[j],f[j-v]+w);
                }
            }
        }
        System.out.println(f[m]);
    }
}

c++版本

   #include <bits/stdc++.h>
using namespace std;

const int N=70,M=32010;
int o=0;
typedef pair<int,int> pii;
int n,m;
pii master[N];

int f[M];

int main(){
    cin>>m>>n;
    vector<pii> servent[N];
    for(int i=1;i<=n;i++){
        int v,p,q;//价格   重要度 住建还是附件
        cin>>v>>p>>q;
        p=p*v;
        if(!q) master[i]={v,p};
        else servent[q].push_back({v,p});
    }
    cout<<servent[2].size()<<endl;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){//分组背包是到1的 多重背包是到一个v[i]。
            //接下来遍历决策，作出决策
            for(int k=0;k<1<<servent[i].size();k++){//二进制遍历每种可能  
                int v=master[i].first,w=master[i].second;
                //计算每种可能的 体积v 和 价值w
                for(int h=0;h<servent[i].size();h++){
                    if(k>>h&1){
                        v+=servent[i][h].first;
                        w+=servent[i][h].second;
                    }
                }
                // cout<<(++o)<<" "<<v<<" "<<w<<endl;
                if(j>=v) f[j]=max(f[j],f[j-v]+w);
            }

        }
        cout<<f[m]<<endl;
    }
    cout<<f[m]<<endl;
    return 0;
}