算法概论实验六

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
实验六
实验目的与要求：掌握动态规划方法的基本思想与设计策略。

1．最长公共子序列问题
【问题描述】
⑴ 给定两个字符串X和Y，设计一个动态规划算法，求出这两个字符串的最长公共子序列，并输出该子序列。

⑵ 若仅要求求出两个字符串的最长公共子序列的长度值，为节省存储空间，采用“滚动数组”方式实现动态规划算法。

2．0-1背包问题
【问题描述】
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W（假定物品重量与背包容量值均为整数），应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？设计一个动态规划算法，求解背包问题。

##The LCS Question
01.jpg-385.6kB

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
// VS2013 CPP CODE
//
#include "stdafx.h"
#include<iostream>
using namespace std;

void PrintLcsPath(int ** b, char * x, int m, int n)
{
	if (m == 0 | n == 0)
		return;
	if (b[m][n] == 1)
	{
		PrintLcsPath(b, x, m - 1, n - 1);
		cout << x[m - 1];
	}
	else if (b[m][n] == 2)
		PrintLcsPath(b, x, m, n - 1);
	else
		PrintLcsPath(b, x, m - 1, n);
}

void print(int ** a, int m, int n)
{
	for (int i = 0; i < m + 1; i++)
	{
		for (int j = 0; j < n + 1; j++)
			cout << a[i][j] << "  ";
		cout << endl;
	}
}

int LcsLength(char *x, char *y, int m, int n)
{
	//创建一个 m+1 * n+1 用于存储LCS
	int **a = new int *[m + 1];
	for (int i = 0; i < m + 1; i++)
		a[i] = new int[n + 1];

	//创建一个 m+1 * n+1 用于存储状态
	//来自于对角线 1 来自于左侧2 来自于上方3
	int **b = new int *[m + 1];
	for (int i = 0; i < m + 1; i++)
		b[i] = new int[n + 1];

	//base case
	for (int i = 0; i < m + 1; i++)
		a[i][0] = 0;
	for (int i = 0; i < n + 1; i++)
		a[0][i] = 0;

	//for
	for (int i =1; i < m + 1;i++)
	{
		for (int j =1; j < n + 1;j++)
		{
			if (x[i-1]==y[j-1])
			{
				a[i][j] = a[i - 1][j - 1] + 1;
				b[i][j] = 1;
			}
			else
			{
				if (a[i-1][j] <= a[i][j-1])
				{
					a[i][j] = a[i][j - 1];
					b[i][j] = 2;
				}
				else
				{
					a[i][j] = a[i - 1][j];
					b[i][j] = 3;
				}
			}
		}
	}
	
	/*print(a, m, n);
	cout << endl;
	print(b, m, n);*/
	cout << "LCS为：";
	PrintLcsPath(b, x, m, n);
	cout << endl;
	return a[m][n];
}
int main()
{
	char x[] = "12312312qwe12312";
	char y[] = "abqweqw123e123123qwcbdab";
	int m = strlen(x);
	int n = strlen(y);
	cout << "LCS的长度为：" << LcsLength(x, y, m, n) << endl;
}

##0-1背包
02.jpg-273.7kB

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// N给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W（假定物品重量与背包容量值均为整数），应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？设计一个动态规划算法，求解背包问题。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

#define W 50

void print(int ** a, int m, int n)
{
	for (int i = 0; i < m + 1; i++)
	{
		for (int j = 0; j < n + 1; j++)
			cout << a[i][j] << "  ";
		cout << endl;
	}
}

void Trackback(int *weight, int n, int w,bool *p,int **a)
{
	if (n==0 || w==0)
		return;
	if (a[w][n]==a[w][n-1])//若和左边的一致，说明没有选最后一个
	{
		p[n - 1] = false;
		Trackback(weight, n - 1, w, p, a);
	}
	else
	{
		p[n - 1] = true;
		Trackback(weight, n - 1, w-weight[n-1], p, a);
	}
}
int getMaxValue(int w, int n, int *price, int * weight )
{
	//创建一个 w+1 * n+1 的二维表
	int **a = new int *[w + 1];
	for (int i = 0; i < w + 1;i++)
	{
		a[i] = new int[n + 1];
	}

	//创建一个数组 记录货物是否取的状态
	bool  *p = new bool[w];
	memset(p, false, sizeof(p));

	//base case
	for (int i = 0; i < w + 1; i++)
		a[i][0] = 0;
	for (int i = 0; i < n + 1; i++)
		a[0][i] = 0;

	//for
	for (int i = 1; i < w + 1;i++)
	{
		for (int j = 1; j < n + 1;j++)
		{
			if (i<weight[j-1])//填写a[i][j]，若当前背包重量小于物品，则不装
			{
				a[i][j] = a[i][j - 1];
			}
			else
			{
				if (a[i][j-1] <= a[i-weight[j-1]][j-1]+price[j-1])
				{
					a[i][j] = a[i - weight[j - 1]][j - 1] + price[j - 1] ;
				}
				else
					a[i][j] = a[i][j - 1];
			}
		}
	}
	//print(a,w,n);

	Trackback(weight, n, w, p, a);
	cout << "从左到右是否取件为：";
	for (int i = 0; i < n; i++)
		cout << p[i] << " ";
	cout << endl;
	return a[w][n];
}

int main()
{
	//int price[] = { 1, 2, 3, 4, 7 };
	//int weight[] = { 2, 4, 5, 6, 210 };
	int price[] = { 60, 100, 120 };
	int weight[] = { 10, 20, 30 };
	cout << "背包问题的解是："<<getMaxValue(W, 5, price, weight) << endl;
	return 0;
}