从1,2,3,......,49,50里选择一个集合S，使得

[单选题]

从1,2,3,......,49,50里选择一个集合S，使得若x属于S，则2x不属于S，则S最多能有____个元素。

```
25
```
```
27
```
```
30
```
```
33
```
```
36
```
```
37
```

查看答案及解析

牛客4848685号

这题核心思想是dynamic programming，我写了一个java代码，可以供大家思考

	public class Solution {



	    public static void main(String[] args){



	     int[] res = new int[50];



	     //base case



	     res[0] = 1;



	     res[1] = 1;



	     int max = 0;



	     for(int i = 2; i <50; i++) {



	                //induction rule: when touch even number



	                //check the difference at index i/2 and i/2-1



	                //and use previous value(at index i-1) minus the difference,



	                // which is cost when you chose the value at index i



	                // and plus 1, which means you add the current value



	      if((i+1)%2==0){



	       res[i] = res[i-1]-(res[i/2]-res[i/2-1])+1;



	      }



	      else{



	       res[i] = res[i-1]+1;



	      }



	                max = Math.max(max,res[i]);



	     }



	     System.out.println(max);



	    }



	}

编辑于 2017-04-26 10:06:15 回复(0)

zhisheng_blog

其实取数的话不一定是唯一的。但是数量是一定的

发表于 2016-10-27 15:00:30 回复(0)

笔墨时光

1到50去一半，取26到50，共25个，1到25去一半，后者全丢弃，取1到12，共12个，其中（1.2.3.4.5.6）*2＝（2.4.6.8.10.12）和后面的进行等销，剩11.9.7，而1-6可删2.3或1.6，剩4个，故：25+3+4＝32，但是要求，最多，所以，1.2.4.8和3.6.12需要进行重新处理，即删除2.4.6，余1.8.3.12，加上前面的11.9.7和5（10）二选一，可得25+4+4

发表于 2018-02-05 11:54:12 回复(0)

鱼的老人

在这里的两种方法我都试了一下都是33个数字。㈠法1:答案是:所有奇数25个，加上部分偶数8个(4.12.16.20.28.36.44.48)。㈡法2:选择一半:答案为26～50加上7～12加上2～3。这两种方法都可以写出明确的算法，并非胡乱抽数字。 ①法1是标记剔除法，刚开始所有数都处于未标记状态，用0表示，有标记后用1表示，再次被标记则从1变成0。第一步标记2的倍数，第二步标记4的倍数，第三步标记8的倍数……第五步标记32的倍数，64大于50无可标记。最后剔除掉所有被标记为1的数。 ②法2是择半选择法，选择一半，剔除这一半对应的一半，不断重复这个过程。选择26到50就必须剔除13到25，选择7到12就必须剔除4到6，选择2到3就必须剔除1。对于更大的数据，希望有大神能在时间复杂度和空间复杂度上，对这两种方法进行分析。

编辑于 2017-03-08 18:59:15 回复(0)

chinasanshi

首先选出26-50共25个数,肯定不会有他们的二倍的数在集合中.同时可以去掉13-25,因为他们的二倍全在26-50中.
剩下1-12.此时类似原问题,选择7-12共6个数(他们的二倍已经被去掉了).同时去掉4-6,也因为他们的二倍都在7-12中.
最后可以选择1,3两个数.
这样总共有25+6+2=33个

发表于 2015-08-24 15:43:12 回复(15)