欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识

S) 然后我们的计算 CAD加密 过程应该是这样 f(0

点击: 次  来源:劳务派遣管理系统 时间:2017-11-29

原文出处: StormMa

媒介

接着上一篇一道题看清动态筹划的前世此生(一),这次我们会以同样的思路去阐明经典的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);
}