1.题目描述：

判断一个数能否通过一个数组中的数相乘而得到（数组中的数使用次数不限）

例如：第一行输入目标数x，第二行再输入一个数组（每个数用空格隔开），如果能则输出1，不能则输出-1；

输入例1：

20

2 3 5 7

输出：

1

解释：20 = 225，可以组成，所以输出1.

输入例2：

20

3 5 7

输出：

-1

解释：无法组成，所以输出-1.

解题思路

2.1错误想法

如20 数组为2，3，5，7
我们把每个数都除到不能整除，举例20/2/2=5 ，5/3不除， 5/5=1结束

1. while((cin >> tmp)){
2. if(x==1)break;
3. while((float)x/(float)tmp - x/tmp ==0){//可以整出没有小数
4. x = x/tmp;
5. }
6. if(cin.get()=='\n'){
7. break;
8. }
9. }
10. if(x==1){
11. cout <<1<<endl;
12. }else{
13. cout <<-1<< endl;
14. }

以上代码对于12 数组6 3 4 不成立，其原因是最终结果 3，4不包含6，而12却可以整除6.
按上面的流程是12/6 =2 ,2/3不整除，2/4不整除。

2.2转换为完全背包问题（使用动态规划解决）

原因分析：对于从 一堆数 中挑选重复若干数 乘积看是否得到某数
类似 在容量限制下，从一堆物品中重复挑若干物品组成价值最高
以12 {6,3,4}为例
大问题12由是否可以由集合元素的乘积得到
变量只有一个：考虑元素的范围{6} {6,3} {6,3,4}
当考虑{6}时 1、6是可以获得的 12因为没有2得到不了26
当考虑{6，3}时 3，6(虽然不是用23而是上面得到6了)，9也可以，12（不可以只有6时得不到加入3要通过4得到，4是没有的）
当考虑{6，3，4}时4,8(不行)，12（可以用4**3得到，3是上面有的）

状态转移公式：
a[x][y] = (a[x][y/集合新加入元素] 或运算|| a[x-1][y]) // 本行左面新加入集合元素位置有没有1，上面一个有没有1
初始时a[1][y]=1

状态转换表格

	1	2	3	4	5	6	7	8	9	10	11	12
{6}	1	0	0	0	0	1	0	0	0	0	0	0因为2不为1
{6,3}	1	0	1	0	0	1（由上面6的1得到⭐）	0	0	0	0	0	0因为4不为1
{6,3,4}	1	0	1	1	0	1	0	0	0	0	0	1根据本行3得到（由本行左侧4个得到⭐）

（因为表格从上往下1只会填补新的空白，所以可以对二维变量a[x][y]优化为一维变量dp[x]）
状态转移公式为：
仅当x%集合新加入元素==0时,可以整除新元素时才
if(x%新加入元素==0)
dp[x] = dp[x/新加入元素] || dp[x] (dp[x]其实就是上一行)

参考代码

1. #include<iostream>
2. #include<cstdio>
3. #include<vector>
4. usingnamespace std;
6. int main(){
7. //freopen("1.in","r",stdin);
8. int x ,tmp;
9. cin >> x;
10. vector<int> dp(x+1,0);
11. dp[1]=1;
12. while((cin >> tmp)){
13. for(int i = tmp; i <= x; i++){
14. if(i % tmp ==0){
15. dp[i]= dp[i]|| dp[i/tmp];
16. }
17. }
19. if(cin.get()=='\n'){
20. break;
21. }
22. }
23. if(dp[x]==1){
24. cout <<1<<endl;
25. }else{
26. cout <<-1<< endl;
27. }
28. return0;
29. }