shopper 油卡如何搞？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

shopper 油卡如何搞？

shopper 油卡如何搞？# PhotoGear - 摄影器材

k*r2011-07-10 07:07

1 楼

这道题不会了，汗。。。是用DP吗？
物品都要放進去,物品跟箱子都算相同
ex.7個物品3個箱子就會有8種:700 610 520 511 430 421 331 322
谢谢。

T*n2011-07-10 07:07

2 楼

Enjoy up to $350 as a new Chase customer
https://accounts.chase.com/raf/share/450676454

r*12011-07-10 07:07

3 楼

谢谢

l*s2011-07-10 07:07

4 楼

C#回溯法，未测试。
public IList> MNCombination(int m, int n)
{
IList> result = new List> result();
combination(result, new List(), 0, m, n);
return result;
}
private void combination(IList> result, IList curLst, int
curSum, int m, int n) //m objects, n buckets
{
if(n == 0 && curSum == m) result.Add(new List(curLst));
else if (n > 0)
{
for(int i = curLst.Count == 0 ? 0 : curLst[curLst.Count - 1]; i +
curSum <= m; i++)
{
curLst.Add(i);
combination(result, curLst, curSum + i, m - i, n - 1);
curLst.RemoveAt(curLst.Count - 1);
}
}
}

d*n2011-07-10 07:07

5 楼

Public都有500甚至600的offer了
楼主自己的refer link还是往后稍稍吧
另外小余版主呢？

r*x2011-07-10 07:07

6 楼

gift card里找你想买的油卡
每个月限$80

【在 r**********1 的大作中提到】

: 谢谢

k*r2011-07-10 07:07

7 楼

seems not correct.
Only the total num is requried. DP should work, but I dont know how.
Thanks,

【在 l******s 的大作中提到】

: C#回溯法，未测试。
: public IList> MNCombination(int m, int n)
: {
: IList> result = new List> result();
: combination(result, new List(), 0, m, n);
: return result;
: }
: private void combination(IList> result, IList curLst, int
: curSum, int m, int n) //m objects, n buckets
: {

o*p2011-07-10 07:07

8 楼

靠这东西赚钱的太low了

【在 d*******n 的大作中提到】

: Public都有500甚至600的offer了
: 楼主自己的refer link还是往后稍稍吧
: 另外小余版主呢？

b*e2011-07-10 07:07

9 楼

f(m, n) = f(m-n,n) + f(m,n-1), if m > 0 and n > 1
f(0,n) = 1, if n > 1
f(m,n) = 0 if m < 0 or n = 0
So:
f(7,3)
= f(4,3) + f(7,2)
= f(1,3) + f(4,2) + f(5,2) + f(7,1)
= 1 + f(2,2) + f(4,1) + f(3,2) + f(5,1) + 1
= 1 + f(0,2) + f(2,1) + 1 + f(1,2) + f(3,1) + 1 + 1
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 8
有了递推式DP是显然的。

【在 k****r 的大作中提到】

: 这道题不会了，汗。。。是用DP吗？
: 物品都要放進去,物品跟箱子都算相同
: ex.7個物品3個箱子就會有8種:700 610 520 511 430 421 331 322
: 谢谢。

k*r2011-07-10 07:07

10 楼

牛人，这怎么解释啊。。。。。为啥可以这样算呢。。。。。。

【在 b***e 的大作中提到】

: f(m, n) = f(m-n,n) + f(m,n-1), if m > 0 and n > 1
: f(0,n) = 1, if n > 1
: f(m,n) = 0 if m < 0 or n = 0
: So:
: f(7,3)
: = f(4,3) + f(7,2)
: = f(1,3) + f(4,2) + f(5,2) + f(7,1)
: = 1 + f(2,2) + f(4,1) + f(3,2) + f(5,1) + 1
: = 1 + f(0,2) + f(2,1) + 1 + f(1,2) + f(3,1) + 1 + 1
: = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

b*e2011-07-10 07:07

11 楼

分情况讨论，m个东西放n个盒子，无非是有空盒子或没空盒子。如果没空盒子，每个盒
子里放一个，剩下的递归；如果有有空盒子，踢掉空盒子，剩下的递归。

【在 k****r 的大作中提到】

: 牛人，这怎么解释啊。。。。。为啥可以这样算呢。。。。。。

k*r2011-07-10 07:07

12 楼

明白了，多谢！

【在 b***e 的大作中提到】

: 分情况讨论，m个东西放n个盒子，无非是有空盒子或没空盒子。如果没空盒子，每个盒
: 子里放一个，剩下的递归；如果有有空盒子，踢掉空盒子，剩下的递归。