回溯法解决子集和数问题

思路

  • 回溯法可以理解成用深度优先算法遍历状态空间树,所以可以使用深度优先递归算法得到解;

  • 定义MAXN为30,即暂时考虑最多有29个元素的集合;

  • 在DFS函数中传入需要的参数:

    TotalWeight:当前子集中所选的元素之和;

    RestWeight:除选出的元素外剩余元素之和;

    x[ ]:问题的一个解,由0和1组成,0代表xi不取,1代表取,1≤i≤n;

    i:当前元素位置;

    n,m,w[ ]:元素个数,和数,和所给集合;

  • 在DFS函数中:

    当TotalWeight与m相等时,输出一个解;

    加上当前元素时还小于m,考虑下一位置元素,继续递归;

    若加上剩余元素时大于m,则不选择当前位置元素,继续递归;

  • 递归结束时,即可得到所有解。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#define MAXN 30
using namespace std;
void Solution_DFS(int TotalWeight, int RestWeight, int x[], int i, int n, int m, int w[]);
//回溯法解决子集和数问题
int main()
{
int n, m;
while (cin >> n >> m)
{
int w[MAXN] = {0};
int RestWeight = 0;
for (int i = 1; i <= n; i++)
{
int temp;
cin >> temp;
w[i] = temp;
RestWeight += temp;
}
int x[MAXN] = {0};
Solution_DFS(0, RestWeight, x, 1, n, m, w);
}
system("pause");
return 0;
}
void Solution_DFS(int TotalWeight, int RestWeight, int x[], int i, int n, int m, int w[])
{
if (i > n)
{
if (TotalWeight == m)
{
for (int i = 1; i <= n; i++)
cout << x[i] << " ";
cout << endl;
}
}
else
{
if (TotalWeight + w[i] <= m)
{
x[i] = 1;
Solution_DFS(TotalWeight + w[i], RestWeight - w[i], x, i + 1, n, m, w);
}
if (TotalWeight + RestWeight > m)
{
x[i] = 0;
Solution_DFS(TotalWeight, RestWeight - w[i], x, i + 1, n, m, w);
}
}
}

Examples

链接:link

num\ N M
1 8 53
2 10 5482
3 21 2463098
4 10 50
5 9 100
6 6 22
7 10 50

动态规划解决矩阵乘法链问题

思路

  • 使用动态规划方法解决矩阵乘法链问题,需在不同大小的子问题的优化值之间建立递归关系,得到最优解;
  • 同时满足优化原理,即优化解包含的子问题的解也是优化解。使用枚举法建立不同长度子问题的优化值之间的递归关系;
  • 求此问题的优化解,即求c(1,n),c(1,n)=min{c(1,k)+c(k+1,n)+r1×r(k+1)×rn},利用此式得到问题的解,再根据每次得到的k值回溯找到优化的乘法顺序;
  • 在代码中,可以使用二维数组存放每次递归关系式中大括号中的每个值,最后找到最小值,即可得到问题的优化解。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
using namespace std;
//动态规划解决矩阵乘法链问题
const int INT_MAX=2147483647;
const int MAXN=10;
void Solution(int *r,int Length,int m[][MAXN],int s[][MAXN]);
void POMCWP(int s[][MAXN],int i,int j);//Acronyms Print Optimal Matrix Chain With Parentheses
int main()
{
int n;
while(cin>>n)
{
int r[MAXN]={0};
for(int i=0;i<n+1;i++)
{
int temp;
cin>>temp;
r[i]=temp;
}
int m[MAXN][MAXN],s[MAXN][MAXN];
Solution(r,n+1,m,s);
cout<<"Minimum: ";
cout<<m[1][n]<<endl;
cout<<"Order: ";
POMCWP(s,1,n);
}
system("pause");
return 0;
}
void Solution(int *r,int Length,int m[][MAXN],int s[][MAXN])
{
int q,n=Length-1;
for(int i=1;i<=n;i++) m[i][i]=0;
for(int l=2;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
m[i][j]=INT_MAX;
for(int k=i;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+r[i-1]*r[k]*r[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
}
void POMCWP(int s[][MAXN],int i,int j)
{
if(i == j) cout<<"M"<<i;
else
{
cout<<"(";
POMCWP(s,i,s[i][j]);
POMCWP(s,s[i][j]+1,j);
cout<<")";
}
}

Examples

Q:p[MAXN]={30,35,15,5,10,20,25};

A:程序输出

1
2
Minimum: 15125
Order: ((M1(M2M3))((M4M5)M6))

Q:p[MAXN]={10,20,50,1,100};

A:程序输出

1
2
Minimum: 2200
Order: ((M1(M2M3))M4)