算法分析
dfs优化主要分成5
类
-
1、优化搜索顺序(大部分情况下,我们应该优先搜索分支较少的结点)
-
2、排除等效冗余
-
3、可行性剪枝
-
4、最优性剪枝
-
5、记忆化搜索
依次遍历所有的猫,通过第u
只猫往现有的k
辆车中放,遍历所有情况
-
第
u
只猫往第1
辆车放 -
第
u
只猫往第2
辆车放 -
…
-
第
u
只猫往第k
辆车放 -
新开一辆车,第
u
只猫往第k + 1
辆车放
优化
-
1、优先放重的猫(优化搜索顺序)
-
2、当前猫
u
放进某辆车时,重量超出m
,剪枝(可信行剪枝) -
3、新开车的数量
k >= ans
,退出(最优化剪枝)
参考文献
算法提高课
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 20;
static int n;
static int m;
static int[] w = new int[N];//每只猫的重量
static int[] sum = new int[N];//表示每个车的重量
static int ans = N;
static void swap(int i,int j)
{
int tmp = w[i];
w[i] = w[j];
w[j] = tmp;
}
static void reverse()
{
int i = 0;
int j = n - 1;
while(i <= j)
{
swap(i,j);
i ++;
j --;
}
}
//准备放第u只猫,车的数量是k
static void dfs(int u,int k)
{
//最优性剪枝
if(k >= ans) return;
if(u == n)
{
ans = k;
return;
}
for(int i = 0;i < k;i ++)
{
//可行性剪枝
if(sum[i] + w[u] <= m)
{
sum[i] += w[u];
dfs(u + 1,k);
sum[i] -= w[u]; //恢复现场
}
}
//新开一辆车
sum[k] = w[u];
dfs(u + 1,k + 1);
sum[k] = 0; //恢复现场
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++) w[i] = scan.nextInt();
//优化搜索顺序
Arrays.sort(w,0,n);
reverse();//翻转函数
dfs(0,0);
System.out.println(ans);
}
}