1.需要分析出来什么情况下不能凑出来的数字是有限个,什么时候不能凑出来的数字是无限多个
举了好几个例子也没发现其中的奥秘。。。
是因为当给定的数不互质的时候,也就是最大公因数d>1,那么n个数字只能凑出来d的整数倍
而当这些数字互质的时候,最大公因数为1,能凑出来的数字就会多,不会是无限多个
**2.状态数组的集合表示和属性
很明显是一个完全背包的问题,一维和二维的情况都是符合的,但是需要明白f[]数组表示的是什么意思
我一开始用f[i]表示从前i个物品里面选,可以凑出来的数目,那么f[i]不一定是只有一个值了,可能是多个
f[i][j] 表示布尔类型的数组,从前i个物品里面选,总和为j的物品可以不可以凑出来
j的取值,可以取得大一点,为100000;
关键是确定集合的表示,最好是从二维状态出发**
3.初始化,这个比较重要,分析出整体的属性之后,确定数组整体初始化成什么(比如一开始存在某些不合法的状态)直接定义为极值 ,在初始化一些特殊情况的值,比如f[0][0]
代码
package dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 包子凑数 {
/**
* 如果ab不互质,也就是最大公约数不为1,那么一定无法凑出最大数
* 反之ab互质,不能凑出的最大的数是(a-1)(b-1)-1
*
* 当有N个数的时候,N个数的不互质,那么不能凑出来的数有无限多个
* N个数互质的时候,最大公因数为1,那么N个数字可以凑出来的数字有很多,不能凑出来的数字就很少
* @param args
*/
static final int N=10010;
public static int gcd(int a,int b) {
return b>0? gcd(b, a%b):a;
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(bufferedReader.readLine());
int a[]=new int [n+1];
int d=0;
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(bufferedReader.readLine());
d=gcd(a[i], d);
}
if(d>1){
System.out.println("INF");
return ;
}
bufferedReader.close();
boolean f[][]=new boolean [n+1][N];
//完全背包问题
f[0][0]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<N;j++){
f[i][j]=f[i-1][j];
if(j >= a[i]){
f[i][j]=f[i][j-a[i]] || f[i][j];
}
}
}
int res=0;
for(int j=0;j<N;j++){
if(!f[n][j]){
res++;
}
}
System.out.println(res);
}
}