@[seanlsy](/user/674247)
您的DP中的第二个判断,在比较与更新g数组是,由于开的是一个新的分组,只需要比较并赋值 $w[j]$ 即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;bool f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return f?x:-x;
}
int f[(1<<18)+5],n,w[20],g[(1<<18)+5],ww;
int main(){
memset(f,127,sizeof f);
f[0]=1;
n=read(),ww=read();
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<=n;i++)
f[1<<i-1]=1,g[1<<i-1]=w[i];
for(int i=1;i<(1<<n);i++)
for(int j=1;j<=n;j++)
if(i&(1<<j-1)){
int kkk=i^(1<<(j-1));
if(w[j]+g[kkk]<=ww&&(f[kkk]<f[i]||(f[kkk]==f[i]&&g[kkk]+w[j]<g[i])))
f[i]=f[kkk],g[i]=g[kkk]+w[j];
else if(w[j]+g[kkk]>ww&&(f[kkk]+1<f[i]||(f[kkk]+1==f[i]&&w[j]<g[i])))
f[i]=f[kkk]+1,g[i]=w[j];
}
printf("%d\n",f[(1<<n)-1]);
return 0;
}
```
by hhiron @ 2022-09-21 22:42:56
@[seanlsy](/user/674247) orz
by _lgh_ @ 2022-09-22 11:32:40
@[hhiron](/user/569131) 感谢大佬,wssb
by seanlsy @ 2022-09-22 11:34:39