感觉这样好理解些

    f[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 1<<m; j++){//若选了第i个物品 则可以更改未来的状态
            f[j|w[i]] = min(f[j|w[i]],f[j]+1);
        }
    }

确实确实，感谢!!!

确实不错

不应该是这样吗？

    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=INF;j>=0;j--){
            dp[j|v[i]]=min(dp[j|v[i]],dp[j]+1);
        }
    }

确实应该逆序

开二维数组的话是这样的（会爆）

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[101][1<<10];
//当前枚举到第几个，哪些种的糖果已经被选中，最小的糖果包数 
int w[101];

int main()
{
    cin>>n>>m>>k;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            int num;
            cin>>num;
            w[i]=w[i]|(1<<(num-1));
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int s=0;s<1<<m;s++)
        {
            dp[i][s]=min(dp[i-1][s],dp[i-1][s^(s&w[i])]+1);
        }   
    }
    if(dp[n][(1<<m)-1]==0x3f3f3f3f) cout<<-1;
    else cout<<dp[n][(1<<m)-1];
    return 0;
}

开滚动数组：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[2][1<<20]; 
int w[101];

int main()
{
    cin>>n>>m>>k;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            int num;
            cin>>num;
            w[i]=w[i]|(1<<(num-1));
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int s=0;s<1<<m;s++)
        {
            dp[i%2][s]=min(dp[(i-1)%2][s],dp[(i-1)%2][s^(s&w[i])]+1);
        }   
    }
    if(dp[n%2][(1<<m)-1]==0x3f3f3f3f) cout<<-1;
    else cout<<dp[n%2][(1<<m)-1];
    return 0;
}

1101|0011 = 1111 然而 1111&(~0011) = 1100

这种情况能确保状态转移是正确的吗

正确的，因为求的是最小值，而1100这个状态必然小于等于1101这个状态的花费

是对的，虽然我前面可能已经有了糖果状态s，我不选择w[i]，导致去掉了我以前的一些糖果，糖果种类为s & (~w[i])，通过不选择使得我的所需凑的糖果种类数量越来越少，所需要·凑的糖果种类数量越来越少，也就越来越好凑出来了，从而所需要的个数也越来越少

具体可以参考下最下面hzx_4的评论，一开始我没有想过这个问题，考研后回来看的评论了解到的

https://www.acwing.com/solution/content/103214/
最后的答案确实是没问题的，但是中间状态有点问题，这里是我一点小见解…

请看一下 https://www.acwing.com/solution/content/103214/

那会不会出现1100不存在但是只有1101存在的状况 ,但是1101这个状态没有被找出来的情况?

我看了评论区的一些看法，我感觉我大致是弄懂了其中的意义。理论上来说，1101|0011 = 1111 然而 1111&(~0011) = 1100，我们这里的是这一轮的状态s与糖果w[i]作用后得出来的，因为1100状态的糖果数一定小于等于1101状态的糖果数，所以这里不会影响，那么问题又来了，我们在前面的遍历中可能根本没有1100这个状态，那么这里会影响结果吗？其实不会的，因为我们遍历的时候，我们的代码写的并不是 “ if((s&w[i])==w[i]) dp[s] = min(dp[s],dp[s & (~w[i])] + 1); ”我们的s并不是包含了w[i]才遍历的，我们的s本身就可以通过w[i]直接变换过来，换句话说，就是比如s=1100，w[i] = 1110，那么我们的上一轮状态就是0，这里就是我前面讲的没有出现过的口味状态情况了，我们在从前向后遍历时，没有出现过的状态也会比他更大的w[i]给被遍历进去，然后我们再在后面s的计算中就又可以涉及到这种实际上没有出现过的状态，等于是逻辑自洽了

谢谢大佬

个人感觉这个题目用背包的思考方式的话，还要枚举更多的状态。如我当前状态时11111,当前的糖果组合为00111，那么按照背包的思想，能被转移的有8种情况。比如11001,11000,11011等，这样复杂度吃不消，所以感觉还是从每个物品可以到达哪个状态出发考虑比较好也就是f[j|w[i]] = min(f[j|w[i]],f[j]+1); 这样

刁

你的代码有问题啊，样例都过不了

样例都没过

s不应该从后往前循环吗

这个一维优化为什么不是让s从1<<m-1开始

弄懂了吗兄弟，我也想问

同问xd

既然 $s$ 是从 $w[i]$ 转移过来的，为什么不要求$s$里包含 $w[i]$ 再去转移呢

for(int i = 1;i<=n;i++)
        for(int s = 0;s < (1 << m);s ++) 
            if((s&w[i])==w[i]) dp[s] = min(dp[s],dp[s & (~w[i])] + 1);//s中包含了w[i] 再去转移

这种方案会漏掉一些解，我试着用这个代码提交过后WA了，事实上这个代码要求s必须包含w[i]，事实上我可以不选则第i包糖果，所以s不一定从w[i]转移过来的，强制加上条件可能会导致漏解

不选第 $i$ 包 糖果时，$s$这个状态本身就不会更新呀。我觉得是因为重复覆盖的问题，即便 $s$ 中不完全包含 $w[i]$，但依然可能会选择 $w[i]$ ，因为 $s$ 可能是先选了 $w[i]$ 然后又去掉了 某些与 $w[i]$ 有交集的物品，导致此时的 $s$ 没办法完全包含 $w[i]$ 但 $s$ 确实可以从 $w[i]$ 来转移

我也想问，同学你弄懂了吗

借楼，贴一种我觉得好理解一点的写法（只稍微改了一点点。。。）

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[1<<20];
int w[101];

int main()
{
    cin>>n>>m>>k;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
        {
            int num;
            cin>>num;
            w[i]=w[i]|(1<<(num-1));
        }
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int s=0;s<1<<m;s++)
            dp[s]=min(dp[s],dp[s^(s&w[i])]+1);
    if(dp[(1<<m)-1]==0x3f3f3f3f) cout<<-1;
    else cout<<dp[(1<<m)-1];
    return 0;
}

s < (1 << m) S
s为啥是这个范围呢

这是为了遍历所用的状态

w[i] |= (1 << num - 1)这个是什么意思

这里是用二进制来表述糖果的选择与否，例如1101，选了1，2，8号糖果

不应该是134号糖果？

01背包一维的得逆序遍历吧，这个得用滚动数组吧

也可以不用吧 其实 把条件该为|用现在这个状态去改变后续状态 这样就不会重复选择当前物品了

tql

牛逼

“那么s & (~w[i])的目的就是先将w[i]的糖果种类去掉,~w[i]按位取非,在与s相于就行了”
我觉得这里并不能直接去掉，因为i之前选的糖果状态可能包含某个糖果，而w[i]也包含这个糖果。（题目说了每包可能有重复的）

没关系的，直接去掉后剩余的糖果越小，在前面就越能凑出来，越容易凑出来说明他的值越小。

最少糖果数量啊

是的这个问题之前并没有好好思考过，可以看看hzx_4的评论，直接去掉后，糖果的种类越来越少，在前面也就越来越容易凑出来了（抱歉哈，之前考研都没刷acwing