首页 > 代码库 > [POJ 2923] Relocation (动态规划 状态压缩)
[POJ 2923] Relocation (动态规划 状态压缩)
题目链接：http://poj.org/problem?id=2923
题目的大概意思是，有两辆车a和b，a车的最大承重为A，b车的最大承重为B。有n个家具需要从一个地方搬运到另一个地方，两辆车同时开，问最少需要搬运几次？
我先想的是我由A车开始搬，搬运能装的最大的家具总重，然后状态压缩记录下搬运了哪些，然后再由B车搬运，状态压缩记录搬运了哪些。以此类推，直到状态满了。
以上方法TLE
然后，实在想不出来了，看了题解：http://blog.csdn.net/woshi250hua/article/details/7636061
也就是说先确定哪些状态是两辆车一次可以搬完的。
怎么确定呢？首先我们先确定出给定状态集合中所有可能出现的并且可以被a车运送的重量，然后看是否存在总重量减去可被a车运送的重量所得到的剩余重量是否能够被b车运送。
如果可以，则这个状态是可以被a，b两辆车一次就送完的。
那么怎么确定给定状态集合中所有可能出现的并且可以被a车运送的重量呢？
这又是一个dp。
设计状态dp[i][j]表示状态集合中的前i个物品是否能够组成j这个重量
如果dp[i-1][j-w[i]]已经出现了（就是说如果存在了重量j-w[i]，我只需要填上重量w[i]就可以形成j），那么dp[i-1][j]就可以组成。
这个问题结束。
对于总问题：
设计状态dp[i][j]表示从前i种已知可以一次搬完的里面搬状态j需要的最少次数。
状态转移：dp[i][j|mask[i]] = min(dp[i-1][j]+1,dp[i-1][j|mask[i]])
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int T;12 int n,c[2];13 int w[22];14 int mask[2222];15 int dp[2222];16 17 bool C(int x){18 bool can[110];19 memset(can,0,sizeof(can));20 can[0] = true;21 int sum = 0;22 for( int i=1;i<=n;i++ )if((x>>(i-1))&1){23 sum += w[i];24 for( int j=c[0];j>=w[i];j--){25 if( can[j-w[i]] ) can[j] = true;26 }27 }28 for(int i=0;i<=c[0];i++){29 if( can[i]&&sum-i<=c[1] ) return true;30 }31 return false;32 }33 34 int main(){35 scanf("%d",&T);36 for(int t=1;t<=T;t++){37 scanf("%d%d%d",&n,&c[0],&c[1]);38 for(int i=1;i<=n;i++) scanf("%d",&w[i]);39 int ptr = 0;40 for(int i=1;i<(1<<n);i++){41 if( C(i) ) mask[++ptr] = i;42 }43 const int INF = 9999;44 fill(dp,dp+2222,INF);45 dp[0] = 0;46 for(int i=1;i<=ptr;i++){47 for(int j=(1<<n)-1;j>=0;j--) if((mask[i]&j)==0) {48 dp[mask[i]|j] = min(dp[mask[i]|j],dp[j]+1);49 }50 }51 printf("Scenario #%d:\n%d\n\n",t,dp[(1<<n)-1]);52 }53 return 0;54 }
[POJ 2923] Relocation (动态规划 状态压缩)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。