装货物-状压dp
程序员文章站
2024-03-23 22:53:58
...
传送门:装货物
要想到状压是求出了所有状态以及每一种状态的不同产生情况,保留每个状态最优的产生情况。
代码:
#include<bits/stdc++.h>
using namespace std;
int w[30];
int dp[2][(1<<21)],p[30];
int main(){
p[0]=1;
for(int i=1;i<=22;++i){
p[i]=p[i-1]*2;
}
int T;
scanf("%d",&T);
while(T--){
int n,x,W;
scanf("%d%d%d",&n,&x,&W);
int Max=0;
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
Max=max(w[i],Max);
}
if(Max>W) {
puts("No");
continue;
}
memset(dp[0],0x3f,sizeof dp[0]);
//for(int i=0;i<=(1<<n)-1;++i) dp[1][i]=W;
dp[0][0]=0;dp[1][0]=0;
for(int i=0;i<=((1<<n)-1);++i){
for(int j=0;j<=n-1;++j){
if(i&p[j]){
continue;
}
if(w[j+1]<=dp[1][i]){
if(dp[0][i]<dp[0][i+p[j]]){
dp[0][i+p[j]]=dp[0][i];
dp[1][i+p[j]]=dp[1][i]-w[j+1];
}
if(dp[0][i]==dp[0][i+p[j]]){
dp[1][i+p[j]]=max(dp[1][i]-w[j+1],dp[1][i+p[j]]);
}
}
else {
if(dp[0][i]+1<dp[0][i+p[j]]){
dp[0][i+p[j]]=dp[0][i]+1;
dp[1][i+p[j]]=W-w[j+1];
}
if(dp[0][i]+1==dp[0][i+p[j]]){
dp[1][i+p[j]]=max(W-w[j+1],dp[1][i+p[j]]);
}
}
}
}
if(dp[0][(1<<n)-1]<=x) puts("Yes");
else puts("No");
}
return 0;
}
上一篇: Python:while循环语句
下一篇: ARouter的介绍和使用