判断一个数能否通过一个数组中的数相乘而得到--类似完全背包问题，动态规划
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结束
while((cin >> tmp)){if(x==1)break;while((float)x/(float)tmp - x/tmp ==0){//可以整出没有小数x = x/tmp;}if(cin.get()=='\n'){break;}}if(x==1){cout <<1<<endl;}else{cout <<-1<< endl;}
以上代码对于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]其实就是上一行)
参考代码
#include<iostream>#include<cstdio>#include<vector>usingnamespace std;int main(){//freopen("1.in","r",stdin);int x ,tmp;cin >> x;vector<int> dp(x+1,0);dp[1]=1;while((cin >> tmp)){for(int i = tmp; i <= x; i++){if(i % tmp ==0){dp[i]= dp[i]|| dp[i/tmp];}}if(cin.get()=='\n'){break;}}if(dp[x]==1){cout <<1<<endl;}else{cout <<-1<< endl;}return0;}