题目链接: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啊啊啊啊~~~~真神奇!!!!

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int INF = 1e9;
const int maxn = + ;
int w[maxn];
int c1, c2, cnt, n;
int dp[<<], state[<<];
// dp[i]:状态为i时需要的最少趟数
// state[i]:两辆车一趟可以运的合理状态 void dfs(int num, int c1, int c2, int s) // s:每一次决策完的状态
{
if (num >= n) // n件物品全部决策完
{
if (!dp[s]) // 这个状态之前没试过
{
dp[s] = ;
state[cnt++] = s;
}
return;
}
if (c1 >= w[num])
dfs(num+, c1-w[num], c2, s|(<<num)); // 尝试装去第一部车上
if (c2 >= w[num])
dfs(num+, c1, c2-w[num], s|(<<num)); // 尝试装去第二部车上
dfs(num+, c1, c2, s); // 两车都不装
} int main()
{
int T, cas = ;
while (scanf("%d", &T) != EOF)
{
while (T--)
{
scanf("%d%d%d", &n, &c1, &c2);
for (int i = ; i < n; i++)
scanf("%d", &w[i]);
memset(dp, , sizeof(dp));
cnt = ;
dfs(, c1, c2, );
for (int i = ; i <= (<<n)-; i++)
dp[i] = (i == ? : INF);
// memset(dp, 0x3f, sizeof(dp));
// dp[0] = 0;
// printf("cnt = %d\n", cnt);
for (int i = ; i < (<<n); i++) // 枚举状态数
{
for (int j = ; j < cnt; j++)
{
if (i & state[j]) // 同一件物品被选了两次,有冲突(真厉害的操作啊~)
continue;
int newstate = i | state[j]; // 新的一个状态
dp[newstate] = min(dp[newstate], dp[i]+);
}
}
printf("Scenario #%d:\n%d\n", ++cas, dp[(<<n)-]);
if (T)
puts("");
}
}
return ;
}

最新文章

  1. js多种切换图片
  2. #include&lt; &gt;和#include""的区别
  3. Container With Most Water——LeetCode
  4. cf C. Vasya and Robot
  5. ubuntu 下编译内核
  6. Gulp browserify livereload
  7. 一点一滴完全突破KAZE特征检测算法,从各向异性扩散滤波开始(1)
  8. 个人开源项目testall 持续更新中&#183;&#183;&#183;
  9. 关于Debug和Release之本质区别的讨论
  10. Python标准库--time模块的详解
  11. Oracle Blob查询和插入
  12. zstu 4247-萌新的旅行
  13. Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem C (Codeforces 831C) - 暴力 - 二分法
  14. P4492 [HAOI2018]苹果树
  15. 利用原生态的(System.Web.Extensions)JavaScriptSerializer将mvc 前台提交到controller序列化复杂对象
  16. 6.翻译:EF基础系列---什么是EF中的实体?
  17. Memcached存Session数据、访问安全性、使用场景总结(3)
  18. 5 Tips for Building a Winning DevOps Culture
  19. 004-ubuntu安装配置SSH服务
  20. 2018.09.28 牛客网contest/197/C期望操作数(状态转移+前缀和递推)

热门文章

  1. 标准C程序设计七---21
  2. Post Content_Length exceeds the limit
  3. Iass、Pass、SasS三种云服务区别?
  4. Java的不定参数(eg:Object...)(转)
  5. centos6.5编译安装gearmand Job Server(C)
  6. aSmack连接server异常smack.SmackException$ ConnectionException thrown by XMPPConnection.connect();
  7. poj2482--Stars in Your Window(扫描线)
  8. mysql中游标在存储过程中的具体使用方法
  9. BFS和DFS记录路径
  10. 【第四篇章-android平台MediaCodec】解决Observer died. Quickly, do something, ... anything...