POJ1011问题TLE，求大老回答
#includeif(dfs(len+a[i],i+1,num+1))return true;
}
else if(len+a[i]==nl){
if(dfs(0,1,num+1))return true;
}
vis[i]=false;
if(len==0)break;
}
return false;
}
int main(){
while(~scanf("%d",&n)){
if(n==0)break;
sum=0,mx=0,k=0;
for(int i=1;i<=n;i++){
int b;
scanf("%d",&b);
if(b>50||b==0)continue;
a[++k]=b;
sum+=b;
mx=max(mx,b);
}
//printf("mx %d sum %d\n",mx,sum);
sort(a+1,a+k+1,cmp);
/*
for(int i=1;i<=n;i++)printf("%d ",a[i]);
printf("\n");
*/
/*
memset(nxt,0,sizeof(nxt));
nxt[k]=k;
for(int i=k-1;i>=1;i--){
if(a[i]==a[i+1])nxt[i]=nxt[i+1];
else nxt[i]=i;
}
*/
int ans=0;
for(int i=mx;i<=(sum>>1)+1;i++){
if(sum%i!=0)continue;
nl=i;
memset(vis,false,sizeof(vis));
if(dfs(0,1,0)){
ans=nl;
break;
}
}
if(ans==0)ans=sum;
printf("%d\n",ans);
}
return 0;
}
你看一下这个代码行不行
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* created by 吴家俊 on 2019/9/17.
*/
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
ArrayList<Integer> list = new ArrayList();
int sum;
while (count != 0) {
sum = 0;
for (int i = 0; i < count; i++) {
int k = scanner.nextInt();
list.add(k);
sum += k;
}
Bar bar = new Bar(list, sum);
bar.inputResult();
count = scanner.nextInt();
//清空list
list.clear();
}
}
}
class Bar {
private ArrayList<Integer> list;//存储被切后各个棒的长度
private int[] visit; //访问数组标记某个数是否被使用过 0未使用 1使用
private int len; //预测最初每个棒的长度
private int n; //最初棒的个数
private int sum; //棒的总长度
private boolean flag; //标记是否得出结果
public Bar(ArrayList<Integer> list, int sum) {
this.list = list;
this.sum = sum;
Collections.sort(list);
Collections.reverse(list); //按棒长降序排序
}
private void init() {
visit = new int[list.size()];
flag = false;
}
public void inputResult() {
for (int i = list.get(0); i <= sum; i++) { //1、缩小len的取值范围
if (i == sum) {
System.out.println(i);
} else if (sum % i == 0) { //2、再次缩小len的取值范围
n = sum / i;
len = i;
init();
dfs(0, len, 0);
if (flag) {
break;
}
}
}
}
/**
* @param index 遍历的起始下标
* @param l 当前剩余长度 为0时 表示凑成了一个原先的棒
* @param now 当前已经凑成的棒的根数 为n时 表示得到解
*/
private void dfs(int index, int l, int now) {
if (flag) return;
if (now >= n) {
flag = true;
System.out.println(len);
return;
}
for (int i = index; i < visit.length; i++) {
if (visit[i] == 0 && l - list.get(i) >= 0) {
visit[i] = 1; //标记已访问
if (l - list.get(i) == 0) { //凑成了一根棒
dfs(0, len, now + 1); //开始寻找下一个棒的起点
} else {
dfs(index + 1, l - list.get(i), now);
}
visit[i] = 0; //还原
if (flag) return;
if (l == len) return; //3、之前的决策有问题，回退到上一根棒的拼凑过程
while (i + 1 < visit.length && list.get(i + 1) == list.get(i)) {//4、该点失败后，后面相同的点不用再尝试
i++;
}
}
}
}
}
搜不到呀，网址发一下