01背包~四次元背包里都会装上什么呢~\(≧▽≦)/

啊w 01背包呐~给出一堆不可拆分的东西,它们有各自的重量和对你来说相应的价值,但是你的背包能装的最大重量是有限的,这个时候要如何选择装哪些东西使得背包里的东西有着最大的总价值呢~

贪心算法

第一种想法则是分别计算出每样东西的单位重量的价值,然后按照降序排序,最后在背包能放的前提下,取单位重量的价值最大的那一件放进去即可w

这种想法则是贪心算法,但是遗憾的是,贪心算法在每件物品不可分的条件下,它不能总是保证背包里的东西有着最大的总价值。例如物品的情况如下表

物品i 重量 价值 单位重量的价值
1 10 60 6
2 20 100 5
3 30 120 4

而背包最大能装下50重量,在这种情况下,按照贪心算法的话,我们会拿A和B,也就是总价值为160~

但是我们稍稍计算一下就知道实际上选择B和C才能使背包里的东西有着最大的总价值,也就是220 www

使用贪心算法求解并不难~按照上面的思路来写就好

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

value  = [60, 100, 120]
weight = [10, 20, 30]
capacity = 50

def greedy(value, weight, capacity):
    """
    0/1 背包 贪心
    """
    import numpy as np
    # 计算每件物品单位重量的价值
    # 为了方便 我们把该物品原始的下标也放进其对应的结果里
    ratio = [[i, value[i]/weight[i]] for i in range(len(value))]
    # 按照单位重量的价值降序排序
    ratio = sorted(ratio, key=lambda x: x[1], reverse=True)
    # 一开始的总价值为 0
    value = 0
    # 一开始都没有放进背包
    choose = np.zeros(len(value))
    for i in range(len(value)):
        # 获取排序之后 某物体的原始下标
        index = int(ratio[i][0])
        # 如果背包能装下该物品
        if capacity - weight[index] >= 0:
            # 装进去~
            # 容量减少
            capacity -= weight[index]
            # 价值增加
            value += value[index]
            # 标记该物品被装进了背包
            choose[index] = 1
    # 返回最后的总价值、有哪些物品被装进去
    return (value, choose)

print(greedy(value, weight, capacity))

穷举算法

那么贪心既然不好用的话,我们就多试试各种组合?也就是穷举所有的可能性w

其实题目的话——01背包——也在暗示我们可以用二进制来表示对这些物品的取舍情况,有 n 个物品的话,就用 n 个 bit 的二进制位就好~

蓝后既然又是二进制的话,每次给那个 n 个 bit 的二进制数 +1 就可以对应一种情况了~随后按照二进制位的 0/1 来判断,找出最大的那一种赋值就好www~

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

value  = [60, 100, 120]
weight = [10, 20, 30]
capacity = 50

def bruteforce(value, weight, capacity):
    """
    0/1背包 暴力搜索
    """
    
    # 最大的价值
    maxv = -1
    # 最大价值所对应的那组选择
    max_group = -1
    
    # 从 0b0 到 0b11..11 (共 len(value) 个 1)
    for i in range(2**len(value)):
        # 当前选择的容量
        current_w = 0
        # 当前选择的价值
        current_v = 0
        # 对应到二进制上
        for b in range(len(value)):
            if (i >> b) & 1:
                # 如果还能装下
                if current_v + value[b] <= capacity:
                    # 继续计算
                    current_w += weight[b]
                    current_v += value[b]
                else:
                    # 否则这组之后的都不用算了
                    break
        # 如果这组的价值比之前的大
        if current_v > maxv:
            # 更新
            maxv = current_v
            max_group = i
    # 返回最大价值和选择
    return (maxv, bin(max_group)[2:])

print(bruteforce(value, weight, capacity))

虽然穷举法可以保证我们找到最优解,但是其复杂度是$O(2^n)$的,物品数量每增加1,计算量就要翻倍∑(゚Д゚)

动态规划

那。。。聪明一点的方法有么~是有的ω

动态规划(Dynamic Programming)的方法就可以做到~

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

value  = [60, 100, 120]
weight = [10, 20, 30]
capacity = 50

def dp(value, weight, capacity):
    """
    0/1背包 动态规划
    """
    import numpy as np
    # 初始化窝们的memo~
    memo = np.zeros((len(value) + 1, capacity + 1))

    # 开始填表w
    # 首先 i 是迭代每一件物品~
    for i in range(0, len(value)):
        # 蓝后是每一种可能的背包剩余重量
        # 这里简化代码,从 [0, capacity] 的每一个数都考虑了
        # 要优化的话,可以从这里下手~
        for j in range(0, capacity + 1):
            # 在不选择第 i 件物品时,无论剩余承重 j 是多少
            # 背包的装的物品的总价值都不会变
            memo[i][j] = memo[i - 1][j]
            
            # 如果剩余容量 j 可以让窝们考虑选不选的话
            if j >= weight[i]:
                # 那么跟窝们之前说的一样
                memo[i][j - weight[i]] = max([memo[i-1][j]+ value[i], memo[i - 1][j - weight[i]]])

    # 最后返回在有 n 件物品时,剩余容量为 0 时的值就可以了
    return memo[len(value) - 1][0]

print(dp(value, weight, capacity))

回溯法

除了动态规划之外,我们还有回溯法~和解决N皇后问题的时候类似~

#include <iostream>
#include <map>
#include <vector>

using namespace std;

/*
输入~
第一行是指有 n 件物品
接下来从第二行起、连续 n 行是这些物品
 第一个数是 weight,第二个数是 value
整个输入的最后一行是背包最大可以装的重量w
5
2 6
2 3
6 5
5 4
4 6
10
 */

struct object {
    int weight;
    int value;
};

/**
 * 01背包w
 *
 * @param capacity       当前背包还能装多少
 * @param value          当前背包里东西的总价值
 * @param i              当前考虑的是下标为 i 的物品是否要放进去
 * @param objects        所有的物品
 * @param take_it_or_not 记录第 i 件物品是否要当进去
 */
pair<int, vector<bool>> backpack(int capacity, int value, int i, const vector<object *> &objects, vector<bool> take_it_or_not) {
    // 我们有米有下标为 i 的物品
    if (i >= objects.size()) {
        // 如果没有就返回当前价值
        return pair<int, vector<bool>>{value, take_it_or_not};
    }
    
    // 有的话,就拿出下标为 i 的物品
    object * current_obj = objects[i];
    
    // 不管背包还能不能装
    // 对于这一件物品,我们都*可以*选择不去装它
    pair<int, vector<bool>> not_take_i = backpack(capacity, value, i + 1, objects, take_it_or_not);
    
    // 如果装不下这件物品的话
    if (current_obj->weight > capacity) {
        // 我们就直接返回不去装它的结果w
        return not_take_i;
    }
    
    // 如果还可以装下这件物品的话
    // 我们就继续看看变化之后(容量减少、价值增加)背包的情况
    pair<int, vector<bool>> take_i = backpack(capacity - current_obj->weight, value + current_obj->value, i + 1, objects, take_it_or_not);
    
    // 比较拿/不拿着一件物品
    if (not_take_i < take_i) {
        // 拿上它的价值更多
        // 那就记下~
        take_i.second[i] = true;
        return take_i;
    } else {
        // 否则就不拿这一件w
        not_take_i.second[i] = false;
        return not_take_i;
    }
}

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<object *> objects;
    // 依次输入 n 件物品
    while (n--) {
        object * obj = new object();
        // 第一个数是 weight,第二个数是 value
        cin >> obj->weight >> obj-> value;
        
        // 放进数组里~
        objects.push_back(obj);
    }
    
    // 记录某一件物品是否要装进背包
    vector<bool> take_it_or_not;
    // 预先调整好大小
    take_it_or_not.resize(objects.size());
    
    // 输入背包的最大重量
    int capacity;
    cin >> capacity;
    
    // 开始尝试吧w
    pair<int, vector<bool>> maximum = backpack(capacity, 0, 0, objects, take_it_or_not);
    printf("maximum: %d\n", maximum.first);
    for (int i = 0; i < maximum.second.size(); i++) {
        printf("%d: %s\n", i, maximum.second[i] ? "YES" : "NO");
    }
}

来下围棋吧~TensorFlow minigo~

TensorFlow 早些天发布了一个名为 minigo 的项目,因为 Google 官方还一直没有开源 AlphaZero,那么就先来看看 minigo 怎么玩(搞事情)吧www

假设乃使用的是 macOS / Ubuntu / debian,当然其他系统也可以,操作大同小异。

首先是安装 Python 3,macOS 下默认是 python2.7,新的 Python 3 需要去 Python 官网下载,https://www.python.org/downloads/。对于 Ubuntu / debian 来说的话,则是直接

apt-get install python3

当然,比较新的 Ubuntu / debian 都会默认安装 python3.6~

接下来需要的是 pip,也就是那个最常被用来安装、管理 Python 包的工具~对于以上三个系统,都可以在terminal中执行如下语句安装w

curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py
python3 get-pip.py

随后就可以用 pip 安装virtualenv了,virtualenv用于隔离不同项目的环境,以避免个项目之间的依赖冲突。

pip3 install virtualenv
pip3 install virtualenvwrapper

之后就可以生成一个用于 minigo 的环境了~

export WORKON_HOME=~/.virtualenvs
export VIRTUALENVWRAPPER_PYTHON=$(which python3)

稍有不同的是,macOS 中,virtualenvwrapper.sh 的安装位置可能不在 /usr/local/bin/virtualenvwrapper.sh。而是在 python3 本体的目录下。于是这里对于 macOS 来说,需要执行的是

export VIRTUALENVWRAPPER_SCRIPT="`dirname $VIRTUALENVWRAPPER_PYTHON`/virtualenvwrapper.sh"

而对于 Ubuntu / debian 则是

export VIRTUALENVWRAPPER_SCRIPT="/usr/local/bin/virtualenvwrapper.sh"

接下来的步骤则都是相同的了~

初始化virtualenvwrapper~指定 python3 创建名为 minigo 的环境

source $VIRTUALENVWRAPPER_SCRIPT
mkvirtualenv -p `which python3` minigo

第一次创建时会自动切换到该环境上,之后需要切换进来则是

source $VIRTUALENVWRAPPER_SCRIPT
workon minigo

现在到正式开始 minigo 的部分了~macOS / Ubuntu / debian 都有自带 git,于是就直接开始w

git clone https://github.com/tensorflow/minigo.git
cd minigo
pip3 install -r requirements.txt

接下来,如果乃的机器上有支持 CUDA 的 GPU 的话,则推荐安装 CUDA9.0,并且用 GPU 版本的 TensorFlow

pip3 install "tensorflow-gpu>=1.5,<1.6"

若不满足条件的话,则是

pip3 install "tensorflow>=1.5,<1.6"

安装好之后,就可以开始设置 minigo 的环境了w

# 用于 cluster/common.sh 的环境变量
PROJECT=minigo-project
source cluster/common.sh

# 我们将训练的模型放在 ~/minigo-models 下
MINIGO_MODELS=$HOME/minigo-models
# 创建一会儿需要的目录
mkdir -p $MINIGO_MODELS
mkdir -p $MINIGO_MODELS/models
mkdir -p $MINIGO_MODELS/data/selfplay
mkdir -p $MINIGO_MODELS/sgf/

# 设置第一个模型的名字
export MODEL_NAME=000000-bootstrap

现在就可以开始第 1 个模型了~

# main.py bootstrap 部分的话,需要两个参数
# 第一个是工作目录,这里我们使用 "." 也就是当前目录
# 第二个是模型保存的路径,这里将前面设置好的变量拼接起来
python3 main.py bootstrap . "\$MINIGO_MODELS/models/$MODEL_NAME"

如果之前的步骤都正确的话,那么输出看上去就是类似这样的w

(minigo) root@minigo:~/minigo# python3 main.py bootstrap . \$MINIGO_MODELS/$MODEL_NAME
See tf.nn.softmax_cross_entropy_with_logits_v2.

Copying ./model.ckpt-1.meta to /root/minigo-models/000000-bootstrap.meta
Copying ./model.ckpt-1.index to /root/minigo-models/000000-bootstrap.index
Copying ./model.ckpt-1.data-00000-of-00001 to /root/minigo-models/000000-bootstrap.data-00000-of-00001
(minigo) root@ minigo:~/minigo# ls /root/minigo-models/
000000-bootstrap.data-00000-of-00001  000000-bootstrap.index  000000-bootstrap.meta

蓝后就可以让 minigo 来进行 selfplay 了~

python3 main.py selfplay "\$MINIGO_MODELS/models/$MODEL_NAME" \
  --readouts 10 \
  -v 3 \
  --output-dir="\$MINIGO_MODELS/data/selfplay/$MODEL_NAME/local_worker" \
  --output-sgf="\$MINIGO_MODELS/sgf/$MODEL_NAME/local_worker"

接下来,让 minigo 在本地进行增强学习的话,我们需要修改一下 rl_loop.py,因为虽然目前官方提供了 local_rl_loop.py,但是里面模型的名字是写死的。

修改的部分在 rl_loop.py 的第 31 行,

# 原本是这样的
# BASE_DIR = "gs://{}".format(BUCKET_NAME)
# 需要修改成下面这样
BASE_DIR = os.environ['MINIGO_MODELS']

修改好之后,则可以不需要Google Cloud Storage就能在本地进行增强学习(其实照着 rl_loop.py 去改 local_rl_loop.py 也行)

python3 rl_loop.py selfplay --readouts=10 -v 2

执行好之后,就可以把数据收集起来了

python3 main.py gather --input-directory="$MINIGO_MODELS/data/selfplay" --output-directory="$MINIGO_MODELS/data/training_chunks"

然后生成新的模型~

export NEXT_MODEL=000001-naive
python3 main.py train . "$MINIGO_MODELS/data/training_chunks" "$MINIGO_MODELS/models/$NEXT_MODEL" --generation-num=1

最后就可以继续在新的模型上训练

# 使用新的模型
export MODEL_NAME=$NEXT_MODEL
# selfplay
python3 main.py selfplay "\$MINIGO_MODELS/models/$MODEL_NAME" \
  --readouts 10 \
  -v 3 \
  --output-dir="\$MINIGO_MODELS/data/selfplay/$MODEL_NAME/local_worker" \
  --output-sgf="\$MINIGO_MODELS/sgf/$MODEL_NAME/local_worker"
# 增强学习
python3 rl_loop.py selfplay --readouts=10 -v 2

在这之后,又可以 gather、生成新模型等等~

如果想和训练好的模型对战的话,则是

LATEST_MODEL=$(ls -d $MINIGO_MODELS/models/* | tail -1 | cut -f 1 -d '.')
python3 main.py gtp -l $LATEST_MODEL -r 10 -v 3

当提示出“GTP engine ready”的时候,就可以开始玩了~

genmove white # 让 minigo 给 white 下一步
play black A1 # 自己给 black 下一步,下在 A1 这个位置
showboard # 查看现在的局面www
minigo
minigo