another fm scam - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PhotoGear - 摄影器材

another fm scam

another fm scam# PhotoGear - 摄影器材

a*l2011-10-09 07:10

1 楼

给一个正整数n，求等分集合1 <= x <= n的所有可能组合。
1. 416题的算法只能确定有没有可能，怎么找到所有可能组合？DFS吗
2. 416题是任意数组，这个特殊数组有没有什么简单解法？

j*n2011-10-09 07:10

2 楼

虽然咨询了医生，说没问题。但是还是想停几天母乳为了保险起见。有没有JM有经验的
？或者说如果是吃药的话，你们一般都会在药停了之后过几天再开始母乳喂养？谢谢！

e*t2011-10-09 07:10

3 楼

http://www.fredmiranda.com/forum/topic/1050758

D*02011-10-09 07:10

4 楼

题目说的是等分数组，所以可以转化成找到和为 sum / 2 的子数组。
回溯法可以找到全部子数组，参考第39题。
没看懂第二问在问什么。
此题代码如下：
class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 == 1) return false;
int tar = sum / 2;
boolean[] dp = new boolean[tar + 1];
dp[0] = true;
for (int n : nums) {
for (int i = tar; i >= n; i--) {
dp[i] = dp[i] || dp[i - n];
}
}
return dp[tar];
}
}

c*r2011-10-09 07:10

5 楼

谁打了疫苗？妈妈还是孩子？
即使妈妈打了也没问题。那个不是病毒。乙肝疫苗是基因重组疫苗。其实就是基因生产
的表面抗原，然后分离纯化的，没有病毒。不会传染的。

k*t2011-10-09 07:10

6 楼

不认识的人PAYPAL GIFT... 蠢蠢蠢蠢蠢蠢蠢蠢
用2% CB的卡, 连CONDITION 不是说的那么好都可以CHARGEBACK. COST 只有1%. 1K 东
西只有$10.

a*l2011-10-09 07:10

7 楼

回溯法就是递归搜索了？再加上DP？416题是特殊knapsack问题或者partition问题，看
上去好像和这个一类，但是416的算法好像在这个题用不上啊。
第二问的意思是，如果这题和416题一类，有没有特殊的解法。因为416针对任意数组，
这个题是特殊的1-N连续整数。

【在 D**********0 的大作中提到】

: 题目说的是等分数组，所以可以转化成找到和为 sum / 2 的子数组。
: 回溯法可以找到全部子数组，参考第39题。
: 没看懂第二问在问什么。
: 此题代码如下：
: class Solution {
: public boolean canPartition(int[] nums) {
: int sum = Arrays.stream(nums).sum();
: if (sum % 2 == 1) return false;
: int tar = sum / 2;
: boolean[] dp = new boolean[tar + 1];

j*n2011-10-09 07:10

8 楼

不好意思没有说清楚。是妈妈打了疫苗。
但我看说明书上说，没有研究证明这个疫苗不会到母乳里面去。那刚打完体内的疫苗剂
量很高我担心影响宝宝。不是怕传染，因为它是死疫苗。

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

: 谁打了疫苗？妈妈还是孩子？
: 即使妈妈打了也没问题。那个不是病毒。乙肝疫苗是基因重组疫苗。其实就是基因生产
: 的表面抗原，然后分离纯化的，没有病毒。不会传染的。

a*o2011-10-09 07:10

9 楼

不认识的还是寄支票靠谱，有个physical address/name基本没问题。

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

: 不认识的人PAYPAL GIFT... 蠢蠢蠢蠢蠢蠢蠢蠢
: 用2% CB的卡, 连CONDITION 不是说的那么好都可以CHARGEBACK. COST 只有1%. 1K 东
: 西只有$10.

D*02011-10-09 07:10

10 楼

我理解是回溯是深搜的一种，递归是函数调用自身的一种思想。
动态规划分为两种：自上而下的叫记忆化搜索
自下而上的是我的代码中用到的，以状态转移方程为主。
如果给定的数组就包括1-N之间的数字的话也许有特殊的解法。
等高人来回答你吧。
反正这道题就是这么做的。蛤蛤蛤蛤蛤蛤蛤。

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

: 回溯法就是递归搜索了？再加上DP？416题是特殊knapsack问题或者partition问题，看
: 上去好像和这个一类，但是416的算法好像在这个题用不上啊。
: 第二问的意思是，如果这题和416题一类，有没有特殊的解法。因为416针对任意数组，
: 这个题是特殊的1-N连续整数。

c*r2011-10-09 07:10

11 楼

mm啊，这个不是死疫苗。就是说，根本没有病毒。只有病毒表面抗原而已。这个抗原是
个蛋白质，是通过基因技术在细菌里面生产的。然后提纯出蛋白质。跟病毒无关。而且
，我们现在常规都是新生儿立刻打乙肝疫苗。既然直接打都没关系，通过母乳进去一点
就更没关系了：）

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

: 不好意思没有说清楚。是妈妈打了疫苗。
: 但我看说明书上说，没有研究证明这个疫苗不会到母乳里面去。那刚打完体内的疫苗剂
: 量很高我担心影响宝宝。不是怕传染，因为它是死疫苗。

o*x2011-10-09 07:10

12 楼

卖家跑出来说话了，先等等看

k*u2011-10-09 07:10

13 楼

X是指x等分？还是只有2等分

n*y2011-10-09 07:10

14 楼

没停

k*u2011-10-09 07:10

15 楼

写416的解法，
bool canPartition(vector& nums) {
int sum = 0;
for(auto num:nums){
sum+= num;
}

if(sum == 0 || sum%2 ==1) return false;

int target = sum/2;
unordered_map pre;
pre[0] = true;

for(auto num:nums){
unordered_map now;
for(auto it: pre){
now[it.first+num] = true;
now[it.first] = true;
if(it.first+num == target) return true;
}
pre = now;
}

return false;
}

j*n2011-10-09 07:10

16 楼

我的ob也说可以打。
可是今天打完了之后我要了那个疫苗盒子里的说明书，上面写的是：
pregnancy category C. It is not known whether vaccine is excreted in human
milk. Because many drugs are excreted in human milk, caution should be
exercised when vaccine is administered to a nursing woman.
所以我才有concern.宝宝现在5周多，只打过第一针HBV疫苗，我们的儿医2个月才打第
二针。不知道我这个MILK里面会含有多少成分给她，会不会影响她的疫苗。所以我想停
几天母乳。是我太多虑了么？刚泵了的奶没敢喂她。

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

: 没停

a*l2011-10-09 07:10

17 楼

x是集合里的数
X = {x: 1, 2, ... N}
等分的意思是两个互不包含的子集的和相等： AUB = X, AxB = O, sum(A) == sum(B)

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

: X是指x等分？还是只有2等分

z*o2011-10-09 07:10

18 楼

1..N
只要sum是偶数是不是总能分开啊?
请证明

a*l2011-10-09 07:10

19 楼

这个不难。
（1）必要性：显然，如果sum是奇数不可能等分。
（2）充分性：对于N>=4可以分N是奇数还是偶数讨论。
N是奇数，x1=1, x1+x_N-1=x_N, 除了这三个数剩下必须要有4k个数，前后各两个每4个
数一组才能抵消，所以必须N=4k+3才能求和等分。
N是偶数，必须N=4k。
集合x=1,2,...N的和是N(N+1)/2。代入4k, 4k+3和是偶数，代入4k+1, 4k+2和是奇数。
只有这4种情况，所以sum是偶数是充分条件。
(1)+(2)所以是充分必要条件。
所以这题如果问能不能等分，要比416题简单，416题是partition problem，要用
pseudo-polynomial algorithm
https://en.wikipedia.org/wiki/Partition_problem
但是这题问的是所以组合，那你就只能搜素了，搜索的时候再想办法优化

【在 z*******o 的大作中提到】

: 1..N
: 只要sum是偶数是不是总能分开啊?
: 请证明