这里二进制枚举的理解：
servent[i]只能取0、1、2，这三个值左移之后对应 –> 1、2、4 再对应到j的取值为 –> (0)、(0, 1)、(0,1,2,3)

然后在最内层循环中，k同样也对应 0、1、2(补充：j的值0、1、2、3 对应到二进制，值分别为 00、01、10、11)

j >> k & 1 意思是 当下方案j情况下，对应的第k个附件是选还是不选(j 此时看做一种方案，即每个位 上0对应不选，1对应选)

我终于懂了，谢谢大佬的解释orz

应该是servent[i].size() 取值范围为[0, 2]，j的取值范围[0, 3]， k的取值范围[0,1]
当j = 0时：k 无论为0还是1，都不取
当j = 1时：k = 0 取， k = 1 不取
当j = 2时：k = 0 不取，k = 1 取
当j = 3时：k = 0 || k = 1 都取
分别对应四种互斥情况

二进制枚举太厉害了。。

确实tql

请问可不可以不用二进制优化？比如像下面这样

#include<bits/stdc++.h>
using namespace std;
vector <int> v[10010],w[66];//价格  重要度
int q[66];
int f[66][33000];
int a[10010],b[66];
int main(){
    int n,m;
    cin>>m>>n;  //m为钱 n为个数
    for(int i = 1; i <= n;i++){//第几个物品
        int x,y;
        cin>>x>>y>>q[i];
        if(q[i]) v[q[i]].push_back(x),w[i].push_back(y);
        else v[i].push_back(x),w[i].push_back(y);
    }
    f[0][0] =0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m;j++){
            if(v[i].size()){
                a[1] = v[i][0],b[1]= w[i][0];       
                a[2] = a[1] + v[i][1],b[2] = b[1] + w[i][1];
                a[3] = a[1] + v[i][2],b[3] = b[1] + w[i][2];        
                a[4] = a[3] + v[i][1],b[4] = b[3] + w[i][1];
                f[i][j] = f[i-1][j];
                for(int k = 1;k <= 4;k++){
                    if(j>=a[k])f[i][j] = max(f[i][j],f[i-1][j-a[k]] + a[k]*b[k]);
                }
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

二进制优化 是通解 你这个和二进制没什么区别 只不过更加具体

这就是二进制枚举

互斥tql

这里

 for (int i = 1; i <= n; i ++ )
        for (int u = m; u >= 0; u -- )
        {
            for (int j = 0; j < 1 << servent[i].size(); j ++ )
            {
                int v = master[i].v, w = master[i].w;
                for (int k = 0; k < servent[i].size(); k ++ )
                    if (j >> k & 1)
                    {
                        v += servent[i][k].v;
                        w += servent[i][k].w;
                    }
                if (u >= v) f[u] = max(f[u], f[u - v] + w);
            }
    }

是不是有master[i]与servent[i]同时为空的情况，这样是不是会多循环。

请问一下我这个代码是不是因为数据太水了呀

#include<bits/stdc++.h>
using namespace std;
const int N = 64005;
int n, m;
int h[N], e[N], ne[N], idx = 0;
int f[100][N];
int v[N], w[N];
int cnt = 100;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}
void dfs(int x)
{
    for(int i = v[x]; i <= m; i += cnt)
        f[x][i] = w[x];
    for(int i = h[x]; ~i; i = ne[i])
    {
        int t = e[i];
        dfs(t);
        for(int j = m; j >= v[x]; j -= cnt)
            for(int k = 0; k <= j - v[x]; k += cnt)
                f[x][j] = max(f[x][j], f[x][j - k] + f[t][k]);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i ++ )
    {
        int q, z;
        scanf("%d%d%d", &v[i], &z, &q);
        w[i] = v[i] * z;
        cnt = __gcd(cnt, v[i]);
        add(q, i);
    }
    dfs(0);
    printf("%d", f[0][m]);
    return 0;
}

就是能过，我去洛谷交了一发也是ac的

我还不是交了的。。。（这样你会不会棕啊）。。。

无所谓，反正又不是比赛

想问下大佬为什么能将j ++ 或者 j – 写成 j += cnt 或者 j -= cnt呀

因为这里我求的是gcd，所以在j+1到j+cnt之间一定没有数，就不用遍历了

现在的数据，我用这样的做法一直tle。。。

数据已经加强了

还是能过

你是不是因为没加cnt啊

话说为什么这种公因数优化是正确的，我添加了 cnt 变量之后，发现 TLE 变成了 AC

这个我解释了的啊

我其实是想问，从复杂度来说，添加 gcd 之后，复杂度会下降多少，为什么数据量这么大也可以通过。

会除以cnt^2

### java版本

import java.util.*;

class PII
{
    int v, w;
    public PII(int v, int w) {this.v = v; this.w = w;}
    public void set(int v, int w) {this.v = v; this.w = w;}
}

public class Main
{
    static Scanner in = new Scanner(System.in);
    static int N = 61, M = 32010;
    static PII master[] = new PII[N];
    static List<PII> servant[] = new ArrayList[N];
    static int f[] = new int[M];

    static
    {
        for (int i = 0; i < N; i++)
        {
            master[i] = new PII(0, 0);
            servant[i] = new ArrayList<PII>();
        }
    }

    public static void main(String args[])
    {
        int m = in.nextInt(), n = in.nextInt();
        for ( int i = 1; i <= n; i++)
        {
            int v = in.nextInt(), w = in.nextInt(), q = in.nextInt();
            if (q == 0) master[i].set(v, v * w);
            else servant[q].add(new PII(v, v * w));
        }

        for (int i = 1; i <= n; i++)
            if (master[i].v != 0)
                for (int j = m; j >= 0; j--)
                    for (int k = 0; k < 1 << servant[i].size(); k++)
                    {
                        int v = master[i].v, w = master[i].w;
                        for (int u = 0; u < servant[i].size(); u++)
                            if ((k >> u & 1) == 1)
                            {
                                v += servant[i].get(u).v;
                                w += servant[i].get(u).w;
                            }
                        if (j >= v) f[j] = Math.max(f[j], f[j - v] + w);
                    }
        System.out.println(f[m]);
    }

}

https://cdn.acwing.com/static/web/img/icons/emoji/thumbsup.png

如果一个包含附件的主件，主件价格为0，附件价格不为0，该情况好像在上述代码中会被直接忽略

已修正～

这样可能会只计算附件的价格不管主件的价格 因为题中重要度是1-5 判断一下重要度是否为0就行了吧 如果为0 说明是附件 就跳过

//因为每个主件的数量只有0，1，2个，
//在01背包基础上，对选择主件，选择主件和一个附件，选择主件和两个附件求最大值即可 
#include <bits/stdc++.h>
using namespace std;
struct wp
{
    int zv,zw,fv1,fw1,fv2,fw2;//主件体积和价值，附件体积和价值 
} a[66] ;
int f[32010];
int n,m,v,p,q;//总钱数 物品数 每件物品特征
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>q;
        if(q==0)//主件
        {
            a[i].zv=v;a[i].zw=v*p;
        }
        else//附件
        {
            if(!a[q].fw1) a[q].fv1=v,a[q].fw1=v*p;//如果是第一附件
            else a[q].fv2=v,a[q].fw2=v*p;//是第二附件
        }
    }
    for(int i=1;i<=m;i++)
        for(int j=n;j>=a[i].zv;j--)
        {
            f[j]=max(f[j],f[j-a[i].zv]+a[i].zw);//选或不选主件
            if(j>=a[i].zv+a[i].fv1) f[j]=max(f[j],f[j-a[i].zv-a[i].fv1]+a[i].zw+a[i].fw1);//选主件和附件1 
            if(j>=a[i].zv+a[i].fv2) f[j]=max(f[j],f[j-a[i].zv-a[i].fv2]+a[i].zw+a[i].fw2);//选主件和附件2
            if(j>=a[i].zv+a[i].fv1+a[i].fv2) f[j]=max(f[j],f[j-a[i].zv-a[i].fv1-a[i].fv2]+a[i].fw1+a[i].fw2+a[i].zw);//选主件和附件1、2 
        }
    cout<<f[n];
    return 0;
}

%%%

# Or2

请问一下为什么不可以选多个主件

#include <bits/stdc++.h>

using namespace std;
typedef long long int LL;
const int N = 3.2e4+10,M =66;
int n,m,f[N];
int cnt;  // 主件个数
int tot[M];  // 每个主件类中附件的个数 
int v[M][5],w[M][5]; 

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==0){
            ++cnt;
            v[cnt][0]=a;
            w[cnt][0]=b*a;
        }else{
            tot[c]++;
            v[c][tot[c]]=a;
            w[c][tot[c]]=b*a;
        }
    }
    for(int i=1;i<=cnt;++i){  // 枚举主件类 
        cout<<v[i][0]<<endl;
        for(int k=n;k>=v[i][0];--k){
            f[k]=max(f[k],f[k-v[i][0]]+w[i][0]);
            if(k>=v[i][0] +v[i][1]+v[i][2]) f[k]=max(f[k],f[k-v[i][0]-v[i][1]-v[i][2]]+w[i][0]+w[i][1]+w[i][2]);
            if(k>=v[i][0] +v[i][1]) f[k]=max(f[k],f[k-v[i][0]-v[i][1]]+w[i][0]+w[i][1]);
            if(k>=v[i][0] +v[i][2]) f[k]=max(f[k],f[k-v[i][0]-v[i][2]]+w[i][0]+w[i][2]);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

请问这样写有什么问题呢?
有近一半数据过不去
二维数组的第一个存主件,第二个第三个存储可能存在的附件

同问，过不去7430那个样例

原因是你的cnt和c不一致，附件无法准确归属到主件（附件归属到了错误的主件）

j >> k & 1这是什么意思啊，一直没看明白

二进制做法，跟状态压缩差不多，就是比如有四个物品，每个物品都看有拿或者不拿两种状态，刚好也就是二进制中的0或者1，然后这四个物品每个物品都有这样的一种状态，然后这个j就是当前十进制的物品状态，如果你要看第k个物品的状态是拿了还是没有拿，你就直接把找到当前物品的状态再右移相应的位数就可以了，这里因为加加上每个物品的状态，所以要判断该物品拿了还是没有拿

明白了，谢谢orz

谢谢兄弟，解释的很清晰。

妙啊

#include<iostream>
#include<algorithm>
#include <vector>

using namespace std;

int f[70][32010];
struct node{
    int x,y;
}master[70];
vector<node> servant[70];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(q==0)
        master[i]={v,p};
        else servant[q].push_back({v,p});

    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<(1<<servant[i].size());k++)
    {
        int v= master[i].x,w=master[i].y;
        for(int u=0;u<servant[i].size();u++)
        if(k>>u&1)
        {
          v+=servant[i][u].x;
          w+=servant[i][u].y;
        }
        if(v>j) f[i][j]=max(f[i][j],f[i-1][j]);
        else f[i][j]=max(f[i][j],f[i-1][j-v]+w);
    }
    cout<<f[n][m];
    return 0;
}

为啥用二维来写就是错的，优化成一维反而对了

应该是当 i是附件的时候f[i][j]不会去更新，i+1的时候用f[i-1]就会出问题吧

二维代码没有问题：

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

typedef pair<int, int> PII;
#define v first
#define w second

const int N = 70, M = 32010;
int n, m;
int f[N][M];
vector<PII> g[N];
PII a[N];

int main() {
    cin >> m >> n;

    for (int i = 1; i <= n; i++) {
        int v, w, p;
        cin >> v >> w >> p;
        if (!p) a[i] = {v, v * w};
        //当该物品为附件时，是不会g数组中单独存储的，就不会出现不选主件而选择了附件的情况
        else
            g[p].push_back({v, v * w});
    }

    // Q:,i-1不一定代表着是主件啊，也有可能是附件，那这样的dp是什么意思呢，我想的是为什么不枚举每一组(也就是每个主件)而枚举1到n确是对的呢
    /*
       A: 首先，明确f[i][j]的含义：在前i个物品中选择，空间最多是j的情况下，最大值
       下面讨论一下：如果i是附件，
       1：它继续了前序的最大值f[i-1][j]
       2: 三层可以进入( 1<<0 =1 ，k层循环是可以进入的，但此时v=w=0,不会产生什么影响)，四层循环不会执行
       综上，f[i-1][j],即使i-1是附件,可它的值仍然是它前面某个主件产生的最大值，从f[i-1][j]继承，和在f[i-x][j]继承是一样一样的
    */
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j]; //不选这个物品

            for (int k = 0; k < 1 << g[i].size(); k++) {
                int v = a[i].v, w = a[i].w;
                for (int x = 0; x < g[i].size(); x++) {
                    if (k >> x & 1) {
                        v += g[i][x].v;
                        w += g[i][x].w;
                    }
                }
                if (j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
            }
        }

    printf("%d\n", f[n][m]);
    return 0;
}

你的写法，应该这样修改：

#include<iostream>
#include<algorithm>
#include <vector>

using namespace std;

int f[70][32010];
struct node{
    int x,y;
}master[70];
vector<node> servant[70];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(q==0)
        master[i]={v,p};
        else servant[q].push_back({v,p});

    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++){
        f[i][j]=f[i-1][j];
        for(int k=0;k<(1<<servant[i].size());k++)
    {
        int v= master[i].x,w=master[i].y;



        for(int u=0;u<servant[i].size();u++)
        if(k>>u&1)
        {
          v+=servant[i][u].x;
          w+=servant[i][u].y;
        }

        if(j>=v) f[i][j]=max(f[i][j],f[i-1][j-v]+w);
    }
    }

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

为什么if(master[i].v)这一段去掉之后不影响结果呢，恕我脑子笨，不明白那一步能把主件为0附件不为0的情况忽略掉

可能使题目数据弱了，y总在这个题的视频切片底下说了不能加
if(master[i].v)因为可能有主件价值为0但附件价值不为0的情况

想问一下，如果把这个dp写成二维是否还能枚举1到n ^^

可以参考这篇题解，使用了一种类似01背包的形式写的 ：https://www.acwing.com/solution/content/16430/

这是那片题解评论区里的一个代码：
Enemy

#include <bits/stdc++.h>
#define v first
#define w second

using namespace std;
typedef pair<int, int> PII;
const int N = 32010, M = 70;

int n, m;
PII fa[M];
vector<PII> son[M];
int f[M][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (!c) fa[i] = {a, a * b};
        else son[c].push_back({a, a * b});
    }

    for (int i = 1; i <= m; i ++ )
    {
        if (fa[i].v)
        {
            // 01背包，先从主件开始放
            for (int j = fa[i].v; j <= n; j ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - fa[i].v] + fa[i].w);

            // 因为push_back的下标是从0开始的，遍历的时候要注意
            // 这部分判断的是，放入当前的主件，对于这个主件的附件用01背包的方式去思考求解
            // 并且当前的f[i][j]一定是已经放入当前主件的情况
            for (int k = 0; k < son[i].size(); k ++ )
                for (int j = n; j >= son[i][k].v; j -- )
                    // 放过主件以后，才能放附件，f为0的部分说明这部分放不进当前的主件
                    if (f[i][j - son[i][k].v] > 0)
                        f[i][j] = max(f[i][j], f[i][j - son[i][k].v] + son[i][k].w);
        }
        // 因为主件和附件要共同判断，但是在综合考虑之前，无法判断和前一个主件哪个更大
        // 注意i不是主件时，也要把状态传递下去
        for (int j = 0; j <= n; j ++ )
            f[i][j] = max(f[i][j], f[i - 1][j]);
    }

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

我刚刚用y总的方法试了一下二维的分组背包，是可以的

#include<bits/stdc++.h>
#define v first
#define w second
using namespace std;
typedef pair<int,int>PII;
const int N=70,M=32010;
int n,m;
int f[N][M];
vector<PII>ve[N];
PII g[N];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int v,w,p;
        cin>>v>>w>>p;
        if(!p) g[i]={v,v*w};
        //当该物品为附件时，是不会g数组中单独存储的，就不会出现不选主件而选择了附件的情况
        else ve[p].push_back({v,v*w});
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选这个物品
            for(int k=0;k<1<<ve[i].size();k++){
                int v=g[i].v,w=g[i].w;
                for(int u=0;u<ve[i].size();u++){
                    if(k>>u&1){
                        v+=ve[i][u].v;
                        w+=ve[i][u].w;
                    }
                }
                if(j>=v) f[i][j]=max(f[i][j],f[i-1][j-v]+w);
            }

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

哦哦，谢谢 但是我有个问题 把该dp写成二维在枚举1到n的时候 若遇到主件这可以进到下面的 k循环，但是在遇到状态转移方程f[i][j]=max(f[i][j],f[i-1][j-v]+w);这个的时候怎么解释呢,i-1不一定代表着是主件啊，也有可能是附件，那这样的dp是什么意思呢，我想的是为什么不枚举每一组(也就是每个主件)而枚举1到n确是对的呢

如果物品是附件的话，是不会被计入$g$数组的，$f[i][j]$代表的是在前i个物品中选总体积为j时的最大价值，如果当前物品$i$为附件的话，$g[i]$={0,0}，执行f[i][j]=max(f[i][j],f[i-1][j-v]+w);实际上就是执行f[i][j]=max(f[i][j],f[i-1][j]);

遇到附件时也会进入k循环，因为1<<0=1，此时v=0,w=0

哦哦，确实能进入k循环，但是不会进入第四成循环，但是我想问一下如果主件在进行状态转移的时候 f[i-1]的含义是什么，i-1不一定是主件啊有可能是附件，可以这样枚举吗，不应该是枚举每一组吗也就是枚举主件吗

i-1不一定时主件，如果i-1是附件的话也会被它上一个主件的值更新掉，因为$f[i][j]$代表的前i个里的最大价值，$f[i][j]=max(f[i][j],f[i-1][j])$一定会让当前物品为附件时的最大价值更新为上一次是主件时的最大价值。
可以模拟一下这两个样例：
1000 2
1001 1 0
10 1 1
和
1000 2
10 1 0
10 1 1
（我语文不好可能表述的不清楚）

嗯嗯，谢谢

%%%%%

唔 为什么这里省掉了视频中的if(master[i].v) 呢

噢噢 刚刚又去仔细地读了下题 应该是题目约束输入时附件必须出现在该主件的后面输入对吧

我看到下面有个评论是：“如果一个包含附件的主件，主件价格为0，附件价格不为0，该情况好像在上述代码中会被直接忽略”。去掉if(master[i].v)应该是补上了这种情况吧。

雀食 ， 刚刚去试了下 就把样例的数据的第一个主件的价格改为0，加 / 不加 if (master[i].v) 是两种结果，但是加了还是a了–>数据应该还没加强~

j >> k & 1
这里是啥意思

表示选取了主件i 的附件集合中的第k个物品