算法实验3《动态规划算法实验》

1. 编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w={2，2，6，5，4},v={6,3,5,4,6} 

      #include<iostream>
      using namespace std;
      void knapsack(int *v, int *w, int c, int n, int**m)
      {
     	int jmax = (w[n] > c) ? c : w[n]-1;
     	for (int j = 0; j <= jmax; j++)m[n][j] = 0;
     	for (int j = w[n]; j <= c; j++)m[n][j] = v[n];
     	for (int i = n - 1; i > 1; i--)
      	{
      		jmax = (w[i] > c) ? c : w[i] - 1;
     		for (int j = 0; j <= jmax; j++)m[i][j] = m[i + 1][j];
     		for (int j = w[n]; j <= c; j++)
      			m[i][j] = (m[i + 1][j] > m[i + 1][j - w[i]] + v[i])   ?   m[i + 1][j]  :  m[i + 1][j - w[i]] + v[i];
      	}
      	m[1][c] = m[2][c];
     	if (c >= w[1])m[1][c] = (m[1][c] > m[2][c - w[1]] + v[1]) ? m[1][c] : m[2][c - w[1]] + v[1];
      }
      int main()
      {
     	int n = 5;
     	int c = 10;
     	int w[6] ={ 0, 2, 2, 6, 5, 4 };
     	int v[6] = { 0, 6, 3, 5, 4, 6 };
     	int **m = new int*[6];
     	for (int i = 0; i < 6; i++)m[i] = new int[6];
     	knapsack(v, w, c, n, m);
      	cout << " 最优值为 " << m[1][c] <<"\n最优解为取第 ";
     	for (int i = 1; i < n; i++)
      	{
     		if (m[i][c] != m[i + 1][c])
      		{
      			cout << i << " ";
      			c -= w[i];
      		}
      	}
     	if (m[n][c])cout << n;
      	cout << " 个物品";
     	system("pause>nul");
     	return 0;
      }
  
 

2. 合唱队形安排问题

【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

      #include<iostream>
      using namespace std;
      //计算以list[i]为结尾的递增数组的最大长度length[i]
      void getLength(int n, double *list, int *length)
      {
      	length[0] = 0;
     	for (int i = 1; i <= n; i++)
      	{
      		length[i] = 0;
     		for(int j=0;j<i;j++)if(list[i]>list[j] && length[i]<length[j]+1)length[i] = length[j] + 1;
      	}
      }
      void change(double *list, int n) //把数组反过来
      {
     	for (int i = 1, j = n; i < j; i++, j--)
      	{
     		double s = list[i] + list[j];
      		list[i] = s - list[i];
      		list[j] = s - list[j];
      	}
      }
      int main()
      {
     	int n;
      	cout << "输入n和n个正数\n";
      	cin >> n;
     	double *list = new double[n + 1];
      	list[0] = 0;
     	for (int i = 1; i <= n; i++)cin >> list[i];
     	int *length1 = new int[n + 1], *length2 = new int[n + 1];
     	getLength(n, list, length1);
     	change(list, n);
     	getLength(n, list, length2);
     	int lengthmax = 0;		//最大长度
     	int index = 0;		//最大长度对应的最大数的下标
     	for (int i = 1; i <= n; i++)
      	{
     		if (length1[i] + length2[n + 1 - i] > lengthmax)
      		{
      			lengthmax = length1[i] + length2[n + 1 - i];
      			index = i;
      		}
      	}
      	cout << "合唱队形最大长度为" << lengthmax-1 << "\n最高者是第" <<index<<"个，高"<< list[index+1];
     	system("pause>nul");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/78868583