环保主题静态网站模板/百度推广有用吗

看了 五大常用算法之一 这篇博文，感觉理解了很多，可是纯粹都是理论，缺少一些示例，所以准备综合一篇博文，以帮助自己记忆，原文：

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html

五、示例

（1）背包问题：

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。

这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

用贪心算法解背包问题的基本步骤：

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

伪代码：

void Knapsack(int n,float M,float v[],float w[],float x[])

{

　　Sort(n,v,w);

　　int i;

　　for (i = 1 ; i <= n ; i++) 

　　　　x[i] = 0;

　　　　float c=M;

　　　　for (i=1;i<=n;i++) {

　　　　　　if (w[i] > c) break;

　　　　x[i]=1;

　　　　c-=w[i];

　　}

　　if (i <= n) 

　　　　x[i]=c / w[i];

}

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。

为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

（2） 哈夫曼算法

代码

/* 主题: Haffman编码
* 作者: chinazhangjie
* 邮箱: chinajiezhang@gmail.com
* 开发环境 : Microsoft Visual Studio 2008
* 时间 : 2010.11.21
*/#include <iostream>
#include <vector>
#include <queue> 
using namespace std ;class HaffmanNode
{
public:HaffmanNode (int nKeyValue, HaffmanNode* pLeft = NULL,HaffmanNode* pRight = NULL){ m_nKeyValue = nKeyValue ;m_pLeft = pLeft ;m_pRight = pRight ;}friend bool operator < (const HaffmanNode& lth, const HaffmanNode& rth){return lth.m_nKeyValue < rth.m_nKeyValue ;}public:int        m_nKeyValue ;    HaffmanNode*    m_pLeft ;HaffmanNode*    m_pRight ;
} ;class HaffmanCoding
{
public:typedef priority_queue<HaffmanNode*> MinHeap ;typedef HaffmanNode*    HaffmanTree ;public:HaffmanCoding (const vector<int>& weight) : m_pTree(NULL){m_stCount = weight.size () ;for (size_t i = 0; i < weight.size() ; ++ i) {m_minheap.push (new HaffmanNode(weight[i], NULL, NULL)) ;}}~ HaffmanCoding(){__destroy (m_pTree) ;}// 按照左1右0编码 void doHaffmanCoding (){vector<int> vnCode(m_stCount-1) ;__constructTree () ;__traverse (m_pTree, 0, vnCode) ;}private:void __destroy(HaffmanTree& ht) {if (ht->m_pLeft != NULL) {__destroy (ht->m_pLeft) ;}if (ht->m_pRight != NULL) {__destroy (ht->m_pRight) ;}if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {// cout << "delete" << endl ;delete ht ;ht = NULL ;}}void __traverse (HaffmanTree ht,int layers, vector<int>& vnCode) {if (ht->m_pLeft != NULL) {vnCode[layers] = 1 ;__traverse (ht->m_pLeft, ++ layers, vnCode) ;-- layers ;}if (ht->m_pRight != NULL) {vnCode[layers] = 0 ;__traverse (ht->m_pRight, ++ layers, vnCode) ;-- layers ;}if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {cout << ht->m_nKeyValue << " coding:  " ;for (int i = 0; i < layers; ++ i) {cout << vnCode[i] << " " ;}cout << endl ;}}void __constructTree (){size_t i = 1 ;while (i < m_stCount) {HaffmanNode* lchild = m_minheap.top () ;m_minheap.pop () ;HaffmanNode* rchild = m_minheap.top () ;m_minheap.pop () ;// 确保左子树的键值大于有子树的键值if (lchild->m_nKeyValue < rchild->m_nKeyValue) {HaffmanNode* temp = lchild ;lchild = rchild ;rchild = temp ;}// 构造新结点HaffmanNode* pNewNode = new HaffmanNode (lchild->m_nKeyValue + rchild->m_nKeyValue,lchild, rchild ) ;m_minheap.push (pNewNode) ;++ i ;}m_pTree = m_minheap.top () ;m_minheap.pop () ;}private:vector<int> m_vnWeight ;    // 权值HaffmanTree m_pTree ;MinHeap        m_minheap ;size_t        m_stCount ;        // 叶结点个数
} ;int main()
{    vector<int> vnWeight ;vnWeight.push_back (45) ;vnWeight.push_back (13) ;vnWeight.push_back (12) ;vnWeight.push_back (16) ;vnWeight.push_back (9) ;vnWeight.push_back (5) ;HaffmanCoding hc (vnWeight) ;hc.doHaffmanCoding () ;return 0 ;
}