设为首页 加入收藏

TOP

一道题看清动态规划的前世今生 ( 二 )(一)
2017-12-07 14:22:18 】 浏览:65
Tags:一道 看清 动态 规划 今生

前言

接着上一篇一道题看清动态规划的前世今生(一),这次我们会以同样的思路去分析经典的01整数背包问题,加深对动态规划的印象。

经典01背包问题

给定n种物品和一个背包。物品i的重量是w[i],其价值位v[i] ,背包的容量为W。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?

暴搜出奇迹

继续我们上一篇的套路来一步一步逼近我们要的动态规划的解法。
假设我们完成了暴搜的函数,我们只需返回结果!

java版

private int search(int idx, int[] w, int[] v, int n, int s, int W) {
	...
}
/**
 * @param w 物品重量 
 * @param v 物品价值
 * @param W 背包的最大容量
 * @return 最大价值
 */
public int solve(int[] w, int[] v, int W) {
    int n = w.length;
    return search(0, w, v, n, 0, W);
}

python版

def search(self, idx, w, v, n, s, W):
	pass
def solve(w, v, W):
    n = len(w)
    return self.search(0, w, v, n, 0, W)

上面的代码,search()函数的idx代表从几号元素开始搜索,s表示,背包已经装了s重量的物品。

那么,很简单,每个物品的状态只有两种,一种就是放入背包,一种就是不放,我们取这两种最大价值的那一个情况,返回即可,很容易完成search()函数的方法体。

java版

private int search(int idx, int[] w, int[] v, int n, int s, int W) {
    // 已经没有物品搜索了
    if (idx >= n) {
        return 0;
    }
    // 如果装不下这件物品,直接返回不拿这件物品的重量即可
    if (s + w[idx] > W) {
        return search(idx + 1, w, v, n, s, W);
    }
    // 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
    return Math.max(search(idx + 1, w, v, n, s + w[idx], W) + v[idx], search(idx + 1, w, v, n, s, W));
}
/**
 * @param w 物品重量
 * @param v 物品价值
 * @param W 背包的最大容量
 * @return 最大价值
 */
public int solve(int[] w, int[] v, int W) {
    int n = w.length;
    return search(0, w, v, n, 0, W);
}

python版

def search(self, idx, w, v, n, s, W):
    # 如果已经搜索完了所有的物品
	if idx >= n:
        return 0
    
    # 如果装不下这件物品,直接返回不拿这件物品的重量即可
    if s + w[idx] > W:
        return self.search(idx + 1, w, v, n, s, W)
    
    # 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
    return max(self.search(idx + 1, w, v, n, s, W), self.search(idx + 1, w, v, n, s + w[idx], W) + v[idx])
def solve(w, v, W):
    n = len(w)
    return self.search(0, w, v, n, 0, W)

关于暴搜代码很简单,只要我们对递归足够了解,我们就很容易写出暴搜!

记忆化搜索

如果看过我前一篇博客的人,大概都知道,下来我们要对状态进行删减,因为上面的代码我们出现了重复计算!你能看出在哪我们重复计算了吗?

假如我们要计算5个物品的最大价值:

w[5] = {4, 3, 2, 5, 1}
v[5] = {3, 4, 1, 4, 2}
W = 10

为了方便起见,search()函数我们简化为f(idx, S)

然后我们的计算过程应该是这样

f(0, 0) = {
    f(1, 4) = {
        f(2, 7) = {
            f(3, 9) = { // ======>
                ...
            },
            f(3, 7) = {
                ...
            }
        },
        f(2, 4) = {
            f(3, 4) = {
                ...
            },
            f(3, 9) = { // ======>
                ...
            }   
        }
    },
    f(1, 0) = {
        f(2, 0) = {
            ...
        },
        f(2, 3) = {
            ...
        }
    }
}

通过上面的验算,我们很容易看出来,f(3, 9)我们计算了两次,所以这就是重复状态,我们应该用个二维数组来存储[idx][S]的值,后面用到直接返回我们上次搜索的结果即可!对吧?我想应该是对的,我相信你也是同意我的!

java版

private int search(int idx, int[] w, int[] v, int n, int s, int W, int[][] memo) {
    // 已经没有物品搜索了
    if (idx >= n) {
        return 0;
    }
    if (memo[idx][s] != -1) {
        return memo[idx][s];
    }
    // 如果装不下这件物品
    if (s + w[idx] > W) {
        return memo[idx][s] = search(idx + 1, w, v, n, s, W, memo);
    }
    // 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
    return memo[idx][s] = Math.max(search(idx + 1, w, v, n, s + w[idx], W, memo) + v[idx], search(idx + 1, w, v, n, s, W, memo));
}
/**
 * @param w 物品重量
 * @param v 物品价值
 * @param W 背包的最大容量 
 * @return 最大价值
 */
public int solve(int[] w, int[] v, int W) {
    int n = w.length;
    final int[][] memo = new int[n][W + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            memo[i][j] = -1;
        }
    }
    return search(0, w, v, n, 0, W, memo);
}

python版

def search(self, idx, w, v, n, s, W, memo):
    # 如果已经搜索完了所有的物品
    if idx >= n:
        return 0
    # 如果装不下这件物品,直接返回不拿这件物品的重量即可
    if memo[idx][s] != -1:
        return memo[idx][s]
    if s + w[idx] > W:
        memo[idx][s] = self.search(idx + 1, w, v, n, s, W, memo)
        return memo[idx][s]
    # 否则我们直接返回拿idx这件物品和不拿这件物品的最大价值就行了!
    memo[idx][s] = max(self.search(idx + 1, w, v, n, s, W, memo),
        self.search(idx + 1, w, v, n,
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Spring、Spring Boot 和 TestNG .. 下一篇没有 redis 也能够支撑”小米在印..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目