三道题理解动态规划

太过爱你忘了你带给我的痛 2022-07-12 07:44 196阅读 0赞

动态规划是算法导论中介绍的最重要的几种基本算法之一，因为好长时间没有看书，再加上原来就理解的不深入，所以早就忘的差不多了，这两天正好因为一道面试题复习一下。

用几句话描述动态规划问题如下：

一个问题可以分解若干子问题，每一个子问题为一种状态，求出每一个状态的最优解，进而在它的帮助下求出下一个状态的最优解。

解决动态规划问题，最重要的步骤就是找出状态转移方程。有了状态转移方程就可以根据初始状态（边界）求出每一个状态的最优解。

动归问题的特点如下：

*  最优子结构
 *  子问题重叠
 *  边界
 *  子问题独立

下面用三道题目帮组理解一下。

# 用最少的硬币得到给定的money #

有1分，3分，5分3种硬币，如何使用最少的硬币数量得到12分。这个题目的状态转移方程如下。

d(i) = min(d(i-v(j)) + 1)

其中d是硬币数量，i是money总数，v(j)是第j个硬币的单位。初始值d(0)=0。代码如下：

#! /usr/bin/env python
        # -*- coding:gbk -*-
    
        class Solution(object):
            def get_min_count(self, money, item_list):
                num_list = {}
                if money == 0:
                    return 0
                num_list[0] = 0
                for i in range(1, money + 1):
                    min = (1<<31) - 1
                    index = -1
                    for j in range(0, len(item_list)):
                        if item_list[j] <= i:
                            if min > num_list[i - item_list[j]] + 1:
                                min = num_list[i - item_list[j]] + 1
                                index = j
                    print "cur_index:%d cur_item:%d pre_index:%d pre_num:%d" \\
                            %(i, item_list[index], i - item_list[index], num_list[i - item_list[index]])
                    num_list[i] = min
    
                return num_list[money]
    
        if __name__ == "__main__":
            s = Solution()
            money = 12
            item_list = [1, 3, 5]
    
            print s.get_min_count(money, item_list)

# 最长升序子数列 #

题目的意思就是从一个数列当中找出最长的升序的子数列，比如”123412345123”的最长升序子数列是”12345”，这个题目的状态转移方程如下。

d(i) = d(i)+1 \[if a\[i\] > a\[j\] i > j\] or d(i) = 1 \[if a\[i\] < a\[j\] i > j\]

其中d是长度，i和j分别代表第i和j个字符，初始值d(0)=0。代码如下：

#! /usr/bin/env python
        # -*- coding:gbk -*-
    
        class Solution(object):
            def max_up_seq(self, seq):
                if len(seq) == 0:
                    return 0
                ret_len = {}
                ret_len[0] = 1
                max_len = 1
                max_seq_start = 0
                for i in range(0, len(seq) - 1):
                    if seq[i + 1] >= seq[i]:
                        ret_len[i+1] = ret_len[i] + 1
                    else:
                        ret_len[i+1] = 1
                        if max_len < ret_len[i]:
                            max_len = ret_len[i]
                            max_seq_start = i - max_len + 1
                if max_len < ret_len[len(seq) - 1]:
                    max_len = ret_len[len(seq) - 1]
                    max_seq_start = len(seq) - max_len
                return seq[max_seq_start:max_seq_start + max_len]
    
        if __name__ == "__main__":
            s = Solution()
            print s.max_up_seq([1,2,3,4])
            print s.max_up_seq([1,2,3,4,2,3,3,4])
            print s.max_up_seq([1,2,1,2,3,4,7,8,9,1,2,4,5,7])

# 0-1背包问题 #

这道题是动态规划最经典的问题，网上求解方法很多。题目内容大致是， 有5个商品，背包的体积为10，他们的体积为 c\[5\] = \{2, 2, 6, 5, 4\}， 价值为 v\[5\] = \{6, 3, 5, 4, 6\}，如何利用背包的体积放入价值最大的物品。一个物品只能放入或者没有放入背包。

状态方程如下。

V\[i\]\[j\]=max(V\[i-1\]\[j\],f\[i-1\]\[j-ci\]+vi)

其中C是背包体积，V\[i\]\[j\]放入第i个物品总体积为j时的总价值，c\[i\]是第i个商品体积，v\[i\]是第i商品价值。代码如下：

# include <cstdio>
    
        const int MAX_NUM = 100;
    
        int V[MAX_NUM][MAX_NUM];
    
        int bag(int volum, int n, int* weight, int* value) {
            if (volum == 0) {
                return 0;
            }
            for (int i = 0; i < n + 1; ++i) {
                V[i][0] = 0;
                // printf("weight:%d value:%d\", weight[i], value[i]);
            }
            for (int i = 0; i < volum + 1; ++i) {
                V[0][i] = 0;
            }
    
            printf("volum:%d num:%d\", volum, n); for (int j = 1; j < volum+1; ++j) { for (int i = 1; i < n+1; ++i) { int max = V[i -1][j]; // printf("max:%d ", max); if (j < weight[i]) { // printf("j<weight[i] "); V[i][j] = V[i - 1][j]; } else { // printf("j>=weight[i] "); if (max < V[i - 1][j - weight[i]] + value[i]) { max = V[i - 1][j - weight[i]] + value[i]; } V[i][j] = max; } printf("%d %d item:%d\", i, j, V[i][j]); } } return 0; } int main() { int weight[6] = {0, 2, 2, 6, 5, 4}; int value[6] = {0, 6, 3, 5, 4, 6}; bag(10, 5, weight, value); printf("max value: %d\", V[5][10]); return 0; }