算法实验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