程序代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

理论辅助:    

#include<stdio.h>

#define MAX_INT 99999
//哈夫曼树和哈夫曼编码的存储表示
typedef struct
{
    int weight;
    int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储哈夫曼树

    
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

#define NUM 10/*
定义物品总数*/
#define CONTENT 10
/*定义包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
    int n=NUM-1;
    int i,j;
    int jMax;
    if((w[n]-1)< c)
    jMax = w[n]-1;
    else
    jMax = c;
    /* 初始化m[n][j] */
    for(j = 0; j <= jMax; j++)
    m[n][j] = 0;
    for(j = jMax +1; j <= c; j++)
    m[n][j] = v[n];
   /*使用非递归的算法来求解m[i][j]
*/
   for(i = n-1; i > 0; i–)
   {
        if((w[i]-1)< c)
        jMax = w[i]-1;
        else
        jMax = c;
        for(j = 0; j <= jMax; j++)
        m[i][j] = m[i+1][j] ;
        for(j = jMax +1; j <= c; j++)
        {
            if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
            m[i][j] = m[i+1][j] ;
        else
        m[i][j] =     m[i+1][j-w[i]]+v[i];
    }
   }
   if(c>w[0])
   {
       if(m[1][c] >= (m[1][c-w[0]]+v[0]))
            m[0][c]=
m[1][c];
       else
        m[0][c]=
m[1][c-w[0]]+v[0];
   }
   else
       m[0][c]=
m[1][c];
    
}
/*寻找最优解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
    int n = NUM -1;
    int i;
    int c = CONTENT;
    for(i = 0; i < n; i++)
    {
        if(m[i][c] ==
m[i+1][c])
            flag[i] = 0;
        else
        {
            flag[i] = 1;
            c-=w[i];
        }
    }
    if(m[n][c] >0)
        flag[n] = 1;
    else
        flag[n] = 0;
}
/* 打印最优解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
    int i;
    printf(“the knapsack should
contain:n”);
    printf(” num weight value n”);
    for(i = 0;i < NUM; i++)
    {
        if(flag[澳门葡萄京官方网站 ,i] ==
1)
                printf(”  %d    %d     %dn”,i,w[i],v[i]);
    }
    printf(“the max value in the knapsack is:
%dn”,m[0][CONTENT]);
}
int main()
{
    int value[NUM]={5,2,3,4,3,6,5,7,8,2};
    int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
    int c = CONTENT;
    int
maxvalue[NUM][CONTENT];
    int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
    clrscr();
    printf(“****************************************n”);
        printf(“*      this program will solve        
*n”);
        printf(“*    the problem of
0-1knapsack        *n”);
        printf(“****************************************n”);
    /*计算最优值*/
    knapsack(value,weight,c,maxvalue);
    /*构造最优解*/
    traceback(flag,weight,maxvalue);
    /*打印程序的结果*/
    printResult(flag,weight,value,maxvalue);
    getch();
    return 0;    
}
    

typedef char **HuffmanCode; //
动态分配数组存储哈夫曼编码表

    
上面这段定义文字是我Copy过来的,目前我还没有那么好的总结能力,呵呵,如果大家对于动态规划不是很熟悉的话,可能看着上面一段文字会不知所云,我一般的学习方法是首先扫描一下基本定义,不深究(有点不求甚解的味道),然后去看一些实例,结合自己的体会,最后再回顾,精读一下定义,这样我对定义才能够真正的理解。下面我们依托一个经典的算法问题来体现上面这段文字的思想,0-1背包问题在算法学习中可谓是必修课程,一般在讲动态规划问题的时候都会用到这个例子。

 

int min(HuffmanTree t,int i)
{
    int j,flag;
    int k=MAX_INT; //
取k为不小于可能的值
    for(j=1; j<=i; j++)
        if(t[j].weight<k&&t[j].parent==0)
            k=t[j].weight,flag=j;
    t[flag].parent=1;//保证下一次min()函数选不到它
    //printf(“%d “,flag);
    return flag;
}

问题描述:

//
s1为最小的两个值中序号小的那个
void select(HuffmanTree
t,int i,int &s1,int &s2)
{
    int j;
    s1=min(t,i);
    s2=min(t,i);//不可能出现s1>s2
    //printf(“s1:%d s2:%dn”,s1,s2);
    if(t[s1].weight>t[s2].weight)//其实这里完全没有必要
    {
        j=s1;
        s1=s2;
        s2=j;
    }
    //printf(“s1:%d s2:%dn”,s1,s2);
}

一个旅行者有一个最多能用M公斤的背包,现在有N件物品,

void PrintHuffmanTree(HuffmanTree
&HT,HuffmanCode &HC, int n)
{
    int i, c, cdlen;
    char *cd;
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//
分配n个字符编码的头指针向量([0]不用)
    cd=(char*)malloc(n*sizeof(char)); //
分配求编码的工作空间
    c=2*n-1;
    cdlen=0;
    for(i=1; i<=c; ++i) HT[i].weight=0; //
遍历赫夫曼树时用作结点状态标志
    while(c)//c是树根所在点,从树根开始遍历,若是叶子则将编码放在数组HC[叶子]
    {
        if(HT[c].weight==0)   //
向左
        {
            HT[c].weight=1;
            if(HT[c].lchild==0 && HT[c].rchild==0)  //
登记叶子结点字符编码
            {
                HC[c]=(char
*)malloc((cdlen+1)*sizeof(char));
                cd[cdlen]=’’;
                strcpy(HC[c],cd); //
复制编码(串)
            }
            if(HT[c].lchild!=0)//想左,给0编码;
            {
                c=HT[c].lchild;
                cd[cdlen++]=’0′;
            }
        }
        else if(HT[c].weight==1)   //
向右
        {
            HT[c].weight=2;
            if(HT[c].rchild!=0) //初始化是叶子节点的左右孩子为空(0),若有孩子不为空,向右编码1;
            {
                c=HT[c].rchild;
                cd[cdlen++]=’1′;
            }
        }
        else
        {

它们的重量分别是W1,W2,…,Wn,

            //HT[c].weight=0;//从左向右退,相当于中序遍历,不会再遍历到哪里了,所以这里没有必要
            c=HT[c].parent;
            –cdlen; // 退到父结点,编码长度减1
        }
    }
    free(cd);
}

它们的价值分别为P1,P2,…,Pn.

//
w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
void
HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
    int m,i,s1,s2;

若每种物品只有一件  
在不超过M公斤的前提下,求旅行者能获得最大总价值的方案。

    HuffmanTree p;

输入格式:

    if(n<=1)   return;
    m=2*n-1;//huffman编码字符都在二叉树的叶子上,全树的节点为叶子节点的2倍-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //
0号单元未用
    for(p=HT+1,i=1;
i<=n; ++i,++p,++w)
    {
        (*p).weight=*w;
        //printf(“%dt%dn”,*w,(*p).weight);
        (*p).parent=0;
        (*p).lchild=0;
        (*p).rchild=0;
    }
    for(; i<=m;
++i,++p)  (*p).parent=0;
    //
在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
    for(i=n+1; i<=m; ++i)   //
建哈夫曼树
    {
        select(HT,i-1,s1,s2);//在i之前挑选最小的和次小的
        HT[s1].parent=HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    //顺序输出哈夫曼树
    PrintHuffmanTree(HT, HC, n);
}

M,N

/*
8
5 29 7 8 14 23 3 11
*/
int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int *w,n,i;

W1,P1

    printf(“Number of weights:”);
    scanf(“%d”,&n);

W2,P2

    w=(int*)malloc(n*sizeof(int));
    printf(“Weights: n”);
    for(i=0; i<n; i++)
        scanf(“%d”,w+i);

……

    HuffmanCoding(HT,HC,w,n);
    printf(“Huffman code:n”);
    for(i=1; i<=n; i++)
    {
        printf(“权为%d的编码是: “,*(w+i-1));
        printf(“%sn”,HC[i]);
    }

问题分析:

}

经过我们粗略的扫描动态规划的定义,我们了解到动态规划问题基本都是通过建立表格,填表格来解决问题的,这里也不例外。

首先我们需要确定表格内部单元格的逻辑关系。

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程便是:

f[i][j] = max{f[i-1][j], f[i-1][j-w[i]]+P[i]}

为什么这里会出现max呢?因为只能从两个状态而来,也就是取和不取当前物品。
我在前i件物品取得重量不超过j的最大价值,是由取不取第i件物品而得到的。对于【将前i件物品放入容量为v的背包中】这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为的背包中”,价值为f[i-1][j];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为j-w[i]的背包中”,此时能获得的最大价值就是f[i-1][j-w[i]]再加上通过放入第i件物品获得的价值P[i]。

下面我们通过一组真实的数据来过一遍算法流程:

测试数据:
10,3
3,4
4,5
5,6

澳门葡萄京官方网站 1

上面这幅图将f[i][j] = max{f[i-1][j],
f[i-1][j-w[i]]+P[i]}
这个式子表现得淋漓尽致..动态规划问题基本都是像这样通过建立表格,填表格来解决问题的。

方案代码:

代码如下(为了能够让更多的人可以阅读代码,采用C语言表达):

 

澳门葡萄京官方网站 2澳门葡萄京官方网站 3View Code

#include<stdio.h>
int c[10][100];
int knapsack(int
m,int n)
{
 int i,j,w[10],p[10];
 for(i=1;i<n+1;i++)
        scanf(“n%d,%d”,&w[i],&p[i]);
 for(i=0;i<10;i++)
      for(j=0;j<100;j++)
           c[i][j]=0;
 for(i=1;i<n+1;i++)
      for(j=1;j<m+1;j++)
           {
            if(w[i]<=j) 
                     {
                      if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
                            c[i][j]=p[i]+c[i-1][j-w[i]];
                            else
                            c[i][j]=c[i-1][j];
                     }
              else c[i][j]=c[i-1][j];
            }
 return(c[n][m]);
                     
}
int main()
{
    int m,n;int i,j;
    scanf(“%d,%d”,&m,&n);
    printf(“Input each one:n”);
    printf(“%d”,knapsack(m,n));
    printf(“n”);
     for(i=0;i<n+1;i++)
      for(j=0;j<m+1;j++)
         {
          printf(“%2d “,c[i][j]);
             if(j==m)printf(“n”);
         }
}


算法实践:

 

问题描述:

Zealot Yin
所在的X公司需要至少W个其他公司提供的外包人员,现在有N家公司向X公司提供了可选方案,其中

P_i代表可提供外包人员单位数,如5人为一个单位数,若选用该公司方案,则必须采用整单位数的人数,如5人为一个单位数,则X公司只能采用n*5个人数(n=0,1,2,….)。C_i代表为P_i单位数员工提供的总工资,单位是万元

输入格式:

N     W

P_i  C_i

请问,采取什么样的方案可以满足X公司花最少的开销招到至少W个外包人员,求出最少的开销金额。

例如X公司需要至少15个外包员工,A公司的价格方案是
2万元/每三人,B公司的价格方案是 3万元/每五人。

输入方案为

2 15
3 2
5 3

得到的最少的开销金额为9万元

分析问题:

这是一个求最优解的问题,与上面的背包问题有些类似,遇到这样的问题我会首先想到使用动态规划的方法来解决问题。同样我们这里建表格来解决问题,这里我们选用一个数组来模拟表格,因为我们在每次输入一个公司的方案的时候就会进行计算当前的最优解,所以我们的建表的承载数据结构只需要一个简单的一维数组就可以解决了。同时数组dp[i]也是至少招i个人员的最佳方案。就像上面的输入数据例子,我们不单只是找出了招15人的解决方案,15人以下的所有最优方案都已经找出来了。也就是说当我们输入3
2的时候,dp数组的最终值的情况如下,其中黑桃表示在当前情况下不可解,a[3]可以认为是代表招3人情况下的最优解,当然a[4]在当前下就是不可解的,这点还是比较好理解。

澳门葡萄京官方网站 4

当输入5  3后,我们dp数组的情况如下:

澳门葡萄京官方网站 5

方案代码:

 

澳门葡萄京官方网站 6澳门葡萄京官方网站 7View Code

#include <stdio.h>
#define MAX 1000000000

int dp[55005];

int min(int
x,int y) { return
x<y?x:y; }

int main()
{
    int n,h;
    int i,j;
    int p,c;
    while(scanf(“%d%d”,&n,&h)==2)
    { 
        dp[0] = 0;
        for ( i = 1 ; i
<= h ; i ++)
        {
            dp[i] = MAX;
        }
        
        for( i = 0 ; i
< n ; i++)
         {           
             scanf(“%d%d”,&p,&c);
             for(j = 0 ;
j<=h ;j++) 
             {
                  if( j + p
> h )  dp[h] = min
(dp[h] , dp[j] + c );
                  else     dp[ j + p ]
= min ( dp[j+p] ,
dp[j] + c ); 
                  
                  char disstr=”x”;
                  printf(“n”);
                  for(int
x=0;x<=h;x++)
                  {   if(dp[x]==1000000000)
                   printf(“%2c
“,disstr);
                   else
                  printf(“%2d
“,dp[x]);
                  }
             }
             printf(“n”);
         }
         
          
         printf(“The Min Value Is %dn”,dp[h]);                       
    }
    
    return 0;
}


 

算法思想总结:

     
动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果,与贪婪算法不同的是,在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列,即问题是否具有最优子结构性质。

 

 

 算法系列目录:

1.递归与分治

2.算法系列总结:贪心算法

3.算法系列总结:动态规划(解公司外包成本问题)

4.算法系列总结:回溯算法(解火力网问题)

5.算法系列总结:分支限界算法