📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1948| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : Fill tank

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurements and a container of 1 litre is always given.
Your job is to fill the tank from source of water using the containers in minimum number of steps.
You cant fill the container with a small amount of water than its size (filling partially is not allowed).
Find the number of steps and print the solution.
e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25
Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25

上一篇:Amazon : find the immediate greater anagram number
下一篇:Google : Eliminate duplicated bit arrays
🔗
 楼主| wwwyhx 2011-7-27 15:13:17 | 只看该作者
全局:
用动态规划,很明显,
和coin change 问题类似, 状态转移方程:

f(i, j) = min{1+f(i-1, j-v[i]) | 2+f(i-1, j-2*v[i]) | ....}

v[n]是容器的容积, f(i,j)是给定容器v[0]..v[i],填满容积为j的容器需要的最少次数

  1. bool Search(int a[], int n, int x)
  2. {
  3.         assert(a && n > 0);

  4.         int nBeg = 0;
  5.         int nEnd = n-1;
  6.         while (nBeg <= nEnd)
  7.         {
  8.                 int nMid = (nBeg + nEnd)/2;
  9.                 if (x == a[nMid])
  10.                         return true;

  11.                 if (x < a[nMid])
  12.                         nEnd = nMid - 1;
  13.                 else
  14.                         nBeg = nMid + 1;
  15.         }

  16.         return false;
  17. }

  18. int PrintBestWay(int a[], int n, int sum)
  19. {
  20.         assert(a && n > 0 && sum > 0 && 1 == a[0]);
  21.        
  22.         int* pRecPre = new int[sum+1];
  23.         int* pRecCur = new int[sum+1];

  24.         for (int i = 0; i <= sum; i++)
  25.                 pRecPre[i] = i;

  26.         for (int i = 1; i < n; i++)
  27.         {
  28.                 for (int j = 0; j <= sum; j++)
  29.                 {
  30.                         if (0 == j)
  31.                         {
  32.                                 pRecCur[0] = 0;
  33.                                 continue;
  34.                         }

  35.                         int nMin = pRecPre[j];
  36.                         for (int k = 1; a[i] * k <= j; k++)
  37.                         {
  38.                                 int nVal = k + pRecPre[j - a[i] * k];
  39.                                 nMin = nVal < nMin ? nVal : nMin;
  40.                         }

  41.                         pRecCur[j] = nMin;
  42.                 }

  43.                 if (i == n-1) break;

  44.                 int* pTmp = pRecPre;
  45.                 pRecPre = pRecCur;
  46.                 pRecCur = pTmp;
  47.         }

  48.         delete []pRecPre;
  49.         int nRet = pRecCur[sum];

  50.         int nCount = 0;
  51.         int x = nRet;
  52.         for (int i = sum; i >= 0; i--)
  53.         {
  54.                 if (pRecCur[i] == x - 1 && Search(a, n, nCount))
  55.                 {
  56.                         cout<<nCount<<" ";
  57.                         x--;
  58.                         nCount = 0;
  59.                 }

  60.                 nCount++;
  61.         }
  62.         cout<<endl;

  63.         delete [] pRecCur;
  64.         return nRet;
  65. }
复制代码
回复

使用道具 举报

🔗
lambda2fei 2012-9-3 15:15:16 | 只看该作者
全局:
wwwyhx 发表于 2011-7-27 15:13
用动态规划,很明显,
和coin change 问题类似, 状态转移方程:

这个dp貌似是O(n*V*V)的,不知道有没更高效解法?
回复

使用道具 举报

🔗
CStick75 2012-9-6 19:16:40 | 只看该作者
全局:
lambda2fei 发表于 2012-9-3 15:15
这个dp貌似是O(n*V*V)的,不知道有没更高效解法?

很显然,暴搜是O(nV)的……………………
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表