时间复杂度 $\mathcal{O}(3^nn^2)$。应该不是因为哪里死循环了，毕竟 10 多秒后还是跑出来了，求助卡常。

输出方案还没写呢。

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#define N 15
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
int n,a[N],f[1<<N][N+1][N+1],to[N][1<<N],sum[1<<N],no[1<<N];
int main(){
	n=15;
	for(int s=0;s<(1<<n);++s){
		for(int i=0;i<n;++i){
			int j;
			for(j=i+1;j<n;++j){
				if((1<<j)&s) break;
			}
			to[i][s]=j;
		}
	}
	for(int cas=read();cas--;){
		n=read();
		for(int i=0;i<n;++i) a[i]=read(),no[1<<i]=i;
		for(int s=0;s<(1<<n);++s){
			for(int i=0;i<=n;++i){
				for(int j=0;j<n;++j){
					f[s][i][j]=1e9;
				}
			}
		}
		for(int s=0;s<(1<<n);++s){
			sum[s]=0;
			for(int i=0;i<n;++i){
				if((1<<i)&s) sum[s]+=a[i];
			}
		}
		for(int s=0;s<(1<<n);++s){
			for(int i=0;i<n;++i){
				if((1<<i)&s) f[s][1][i]=sum[s];
			}
		}
		for(int s=0;s<(1<<n);++s){
			for(int i=2;i<=n;++i){
				for(int t=(s-1)&s;t;t=(t-1)&s){
					int tmp=t;
					while(tmp){
						int j=no[tmp&-tmp];
						if(sum[s^t]>f[t][i-1][j]){
							f[s][i][to[j][s^t]]=min(f[s][i][to[j][s^t]],sum[s^t]);
						}
						tmp-=(tmp&-tmp);
					}
				}
			}
		}
		int ans=1e9;
		for(int i=n;i>=1;--i){
			for(int j=0;j<n;++j){
				if(f[(1<<n)-1][i][j]<1e9){
					if(n-i<ans){
						ans=n-i;
						break;
					}
				}
			}
			if(ans!=1e9) break;
		}
		printf("%d\n",ans);
	}
	return 0;
}