首页 > 代码库 > poj 2923 Relocation 解题报告
poj 2923 Relocation 解题报告
题目链接：http://poj.org/problem?id=2923
题目意思：给出两部卡车能装的最大容量，还有n件物品的分别的weight。问以最优方式装入，最少能运送的次数是多少。
二进制表示物品状态：0表示没运走，1表示已被运走。
枚举出两辆车一趟可以运出的状态。由于物品是一趟一趟运出来的。所以就可以由一个状态通过两辆车一趟的状态转移到另一个状态。
dp[i]=MIN(dp[k]+1)。k可以由两车一趟转移到i。
我是参考此人的：http://blog.csdn.net/bossup/article/details/9363845
状态压缩DP啊啊啊啊~~~~真神奇！！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 1e9; 8 const int maxn = 100 + 5; 9 int w[maxn];10 int c1, c2, cnt, n;11 int dp[1<<10], state[1<<10]; 12 // dp[i]：状态为i时需要的最少趟数13 // state[i]：两辆车一趟可以运的合理状态14 15 void dfs(int num, int c1, int c2, int s) // s：每一次决策完的状态16 {17 if (num >= n) // n件物品全部决策完18 {19 if (!dp[s]) // 这个状态之前没试过20 {21 dp[s] = 1;22 state[cnt++] = s; 23 }24 return;25 }26 if (c1 >= w[num])27 dfs(num+1, c1-w[num], c2, s|(1<<num)); // 尝试装去第一部车上 28 if (c2 >= w[num])29 dfs(num+1, c1, c2-w[num], s|(1<<num)); // 尝试装去第二部车上30 dfs(num+1, c1, c2, s); // 两车都不装31 }32 33 int main()34 {35 int T, cas = 0;36 while (scanf("%d", &T) != EOF)37 {38 while (T--)39 {40 scanf("%d%d%d", &n, &c1, &c2);41 for (int i = 0; i < n; i++)42 scanf("%d", &w[i]);43 memset(dp, 0, sizeof(dp));44 cnt = 0;45 dfs(0, c1, c2, 0);46 for (int i = 0; i <= (1<<n)-1; i++)47 dp[i] = (i == 0 ? 0 : INF);48 // memset(dp, 0x3f, sizeof(dp));49 // dp[0] = 0;50 // printf("cnt = %d\n", cnt);51 for (int i = 0; i < (1<<n); i++) // 枚举状态数52 {53 for (int j = 0; j < cnt; j++)54 {55 if (i & state[j]) // 同一件物品被选了两次，有冲突（真厉害的操作啊~）56 continue;57 int newstate = i | state[j]; // 新的一个状态58 dp[newstate] = min(dp[newstate], dp[i]+1);59 }60 }61 printf("Scenario #%d:\n%d\n", ++cas, dp[(1<<n)-1]);62 if (T)63 puts("");64 }65 }66 return 0;67 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。