问题描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个孩子的结点）。这棵树共有n个结点（叶子点或者树枝分叉点），编号为1~n，树根编号一定是1。

现在这棵树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量P，求出最多能留住多少苹果。

要求：

(1) 创建合适的数据结构存储树的信息。

(2) 设计问题的递归公式。

(3) 实现动态规划算法，输出保留的树枝数量P和最多留住的苹果数。

问题分析

本题不仅涉及到动态规划的算法，还涉及到了数据结构-树。

首先，需要找一种树的存储方法，其次，为方便计算，将节点与树的枝条连在一起计算。

节点本身需要一个挂在树上的枝条，接下来是分类讨论它的左右孩子所有拥有的枝条数对应的最大苹果树。

使用一位数组存树，2i即为其左子树，2i+1即为其右子树

这类问题就是通过将大问题化解为同类小问题，找到递推入口(即从叶子节点)，并从入口向目标求解递推

算法设计：

  1. 储存树

    由于题目给的是极其类似满二叉树的结构，故不使用递归的方法构造树，而采用一维数组，用少量空间换取大量时间。构造树的时间为线性时间n

  2. 初始化运算表

    将每个节点所拥有一到p个枝条时最大苹果树用二位数组存放。C++构造二维数组所花线性时间为n

    从子叶节点(递推入口开始)开始，对于子叶节点拥有一到p个枝条，苹果数值均为其本身苹果数。

    枝条为零的情况下，所有节点所含苹果数为零

  3. 设计递推

    递推方程式为 f[i][j] = max(f[i][j],f[i2][k]+f[i2+1][j-1-k]+ value[i]);

    采用双重循环，求出每个节点从1到p枝条时的最大所含苹果数。所用时间n^p

  4. 得出结果

    f[i] [p+1]即位整棵树最大苹果数。

  5. 总时间复杂度分析

    T= t(初始化)+t(递推) = O(n^2)

参考代码

#include <bits/stdc++.h>
using namespace std;
int string_to_number(string s){
	stringstream ss(s) ;
	int a = 0 ;
	ss >> a ;
	return a ;
}
int main(int argc, char const *argv[])
{
	int number = 0 , p = 0 ;
	//文件操作一
	ifstream in("apple.txt");
    string line;
    if(!in)  { cout << "打开文件出错" << endl; return 0 ; }
	getline(in,line);
	number = string_to_number(line);
	line.clear();
	getline(in,line);
	p = string_to_number(line);

	vector<int> value(number+1);
	//文件操作二
	for(int i = 1 ; i < number+1 ; ++i){ line.clear() ; getline(in,line); value[i] = string_to_number(line);}
	vector< vector<int> > f(number+1);
	for(int i = 1 ; i < number + 1 ; ++i){f[i].resize(p+2);}
    //初始化
	for(int i = 1 ; i < number + 1 ; ++i){f[i][0] = 0 ; f[i][1] = value[i];}
	for(int i = number  ; i >= 1; --i ){
		for(int j = 2 ; j <= p + 1 ; ++j){
			for(int k = 0 ; k < j ; ++k){
			 if(i*2 <= number){f[i][j] = max(f[i][j],f[i*2][k]+f[i*2+1][j-1-k]+ value[i]);}
		    //没有左子树以及右子树，则该值为其本身价值
			else{f[i][j] = value[i] ;}
		 }
		}
	}
	cout << f[1][p+1];
	return 0;
}

谢谢访问