poj 2923 状压dp+01背包

时间:2023-04-27 09:09:08

好牛b的思路

题意:一系列物品,用二辆车运送,求运送完所需的最小次数,两辆车必须一起走

解法为状态压缩DP+背包,
本题的解题思路是先枚举选择若干个时的状态,
总状态量为1<<n,判断这些状态集合里的那些物品能否一次就
运走,如果能运走,那就把这个状态看成一个物品。预处理完能
从枚举中找到tot个物品,再用这tol个物品中没有交集
(也就是两个状态不能同时含有一个物品)的物品进
行01背包,每个物品的体积是state[i],价值是1,求
包含n个物品的最少价值也就是dp[(1<<n)-1](dp[i]表示状态i需要运的最少次数)。

状态转移方程:dp[j|k] = min(dp[j|k],dp[k]+1) (k为state[i,1<=j<=(1<<n)-1])。
算法复杂度O((2^N)*N)

 #include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
int state[];
int tol;
int dp[];
int n,C1,C2;
int cost[];
bool vis[]; bool judge(int x)
{
int sum=;
memset(vis,false,sizeof(vis));
vis[]=true;
for(int i=;i<n;i++)
{
if((<<i)&x)
{
sum+=cost[i];
for(int j=C1;j>=cost[i];j--)
if(vis[j-cost[i]])
vis[j]=true;
}
}
if(sum>C1+C2)return false;
for(int i=;i<=C1;i++)
if(vis[i]&&sum-i<=C2)
return true;
return false;
}
int main()
{
int T;
int iCase=;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d%d%d",&n,&C1,&C2);
for(int i=;i<n;i++)
scanf("%d",&cost[i]);
for(int i=;i<(<<n);i++)dp[i]=INF;
dp[]=;
tol=;
for(int i=;i<(<<n);i++)
if(judge(i))
state[tol++]=i;
for(int i=;i<tol;i++)
for(int j=(<<n)-;j>=;j--)
{
if(dp[j]==INF)continue;
if((j&state[i])==)
{
dp[j|state[i]]=min(dp[j|state[i]],dp[j]+);
}
}
printf("Scenario #%d:\n%d\n\n",iCase,dp[(<<n)-]);
}
return ;
}