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

[CareerCup] CareerCup 8.7

🔗
writecoffee1 2012-8-2 04:35:13 | 只看该作者
全局:
https://github.com/writecoffee/c ... blob/master/8.7.cpp

这个够简洁的 哈哈 不知道有没有了解完全背包 有兴趣可以看看
就这个题 常数个物品来说 时间可到 O(n) 滚动数组优化空间到 O(n)
       public static int __8_7(int n) {
                int[] values = {1, 5, 10, 25};
                int[] f = new int[n+1];
                f[0] = 1;
                for (int v: values) {
                        for (int i = v; i <= n; ++i) {
                                f += f[i-v];
                        }
                }
                return f[n];
        }

背包问题啥都不懂,我先把基础搞搞好了.... (还是先mark一下)

1.
• Subdivide the problem into smaller problems in a descending way as each denomination
could be expressed by itself or ones that are smaller than it.
• Accumulate the expression ways in an ascending way after finish.
2. Leap in
• In each level’s make change, the number of ways for sub-dividing is n / denomin + 1, where
denomin is the step width for each iteration. But note that if the nxt de is not 1, its credit
should be substitued by its sub-level make change.
回复

使用道具 举报

🔗
modifiedname 2012-8-2 05:12:07 | 只看该作者
全局:
这题有没有代数解啊?貌似小学数学竞赛的时候见过这种无数次
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-2 21:48:45 | 只看该作者
全局:
writecoffee1 发表于 2012-8-2 04:35
https://github.com/writecoffee/career_cup_iteration/blob/master/8.7.cpp

有一个叫“背包问题九讲”挺好的
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-2 21:52:49 | 只看该作者
全局:
小K 发表于 2012-8-2 05:12
这题有没有代数解啊?貌似小学数学竞赛的时候见过这种无数次

问了一个数学挺好的同学 他说
“数学方法应该是生成函数,但计算起来的话,复杂度不会下降,基本上等同于DP
当然,这个问题确实有更高明的方法,但是会非常复杂”
回复

使用道具 举报

🔗
leonsu777 2012-8-8 00:33:36 | 只看该作者
全局:
https://gist.github.com/3286853
initial                             quarter                        dime
makeChange(100, 0) -> makeChange(100, 0) ->makeChange(100, 0, 0) -> ::::::
                                                                       ->makeChange(100, 0, 1) -> ::::::
                                                                       .....                                                                        
                                   -> make(100,1)
                                    ...

It is a tree like recursion.
base case is the full reduce statement, return 1;
Cache the result of last denomination, and recusive work on the makeChange(rest_of_value, next_denom)

战拖!!
回复

使用道具 举报

🔗
lml 2012-8-21 04:36:08 | 只看该作者
全局:
类似图搜索,似乎没有多项式级别复杂度,只有幂级数复杂度,但可以通过剪枝优化。
https://github.com/zyli5313/CareerCup/blob/master/ch8/8-7.cpp
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-21 13:31:49 | 只看该作者
全局:
lml 发表于 2012-8-21 04:36
类似图搜索,似乎没有多项式级别复杂度,只有幂级数复杂度,但可以通过剪枝优化。
https://github.com/zyl ...

既然提到图,那说这个是 DAG 上的动态规划好了
就算是搜索 前面的同学也写了多项式时间的算法,n 个物品也可以
回复

使用道具 举报

🔗
lml 2012-8-21 23:22:47 | 只看该作者
全局:
BinaryWitch 发表于 2012-8-21 13:31
既然提到图,那说这个是 DAG 上的动态规划好了
就算是搜索 前面的同学也写了多项式时间的算法,n 个物品 ...

多谢 背包问题九讲 这个信息。我看了下,发现9楼的那个似乎不对吧,这个不是背包问题吧,是子集合问题吧(http://love-oriented.com/pack/P11.html)因为硬币找钱并没有weight啊,cost是你写的values,哪个是weight呢?子集合问题才是找钱的这种没有weight的吧?

而且即使对,似乎初始化也有点问题,你初始化所有数组为0,这个不是恰好装满,是<=V的(http://love-oriented.com/pack/P01.html)。

能给我说下子集合问题和完全背包的不同么?thx
回复

使用道具 举报

🔗
 楼主| BinaryWitch 2012-8-22 00:42:05 | 只看该作者
全局:
lml 发表于 2012-8-21 23:22
多谢 背包问题九讲 这个信息。我看了下,发现9楼的那个似乎不对吧,这个不是背包问题吧,是子集合问题吧( ...

背包问题也是 NPC
子集和问题可以规约到背包问题
这个确实不是朴素的背包和子集和 不过可以看成变形吧
9 楼把 f[0] 初始化为 1 了
f += f[i-v] 这句确实漏了下标...
完全背包是每个物品无限个嘛


回复

使用道具 举报

🔗
lml 2012-8-22 01:12:44 | 只看该作者
全局:
BinaryWitch 发表于 2012-8-22 00:42
背包问题也是 NPC
子集和问题可以规约到背包问题
这个确实不是朴素的背包和子集和 不过可以看成变形吧
...

f[i] += f[i-v],这个没看懂,这个求的是个数吧,但为什么呢?

感觉这个题和http://love-oriented.com/pack/P11.html子集合里面的描述好像啊
回复

使用道具 举报

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

本版积分规则

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