Sparse skills

CS skills

Git study

Knapsack Problem

你有一个容量为 W=10 的背包，以及以下物品：

物品	重量（kg）	价值（元）
物品 1	2	6
物品 2	3	10
物品 3	4	12

目标是选择物品装入背包，使得总价值最大，同时不超过背包容量。

动态规划：

步骤:

1. 定义状态

用 dp[i][w]表示在前 i 个物品中，容量不超过 w 时的最大价值。

2. 状态转移方程

如果不选择第i个物品: dp[i][w] = dp[i-1][w]

如果选择第i个物品: dp[i][w] = dp[i-1][w-weight[i]]+value[i]

3. 初始化

当i = 0 或 w = 0, 即没有物品或背包容量为 0 时: dp[i][w]=0

4. 最终结果

dp[n][W] 表示在前 n 个物品中，容量不超过 W 时的最大价值。


def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

# 示例数据
weights = [2, 3, 4]
values = [6, 10, 12]
W = 10

print("最大价值为:", knapsack(weights, values, W))

如果背包问题变成连续空间呢？

YARN

Yet Another Resource Negotiator

YARN 的核心组件

1. ResourceManager (RM)
   • 集群范围的资源管理器，负责协调整个集群的资源分配。
   • 包含两个主要模块：
     • Scheduler：根据调度策略为应用程序分配资源。
     • ApplicationsManager：负责应用程序的生命周期管理，比如启动 ApplicationMaster。
2. NodeManager (NM)
   • 每个节点上的代理，负责单节点资源的管理和任务的执行。
   • 监控容器（Container）的资源使用（CPU、内存等）并报告给 ResourceManager。
3. ApplicationMaster (AM)
   • 每个应用程序的具体作业管理器，负责作业的调度和任务执行的管理。
   • 通过与 ResourceManager 和 NodeManager 通信来请求资源和启动任务。
4. Container
   • YARN 中的最小资源分配单元，包含一定数量的 CPU 核心和内存。
   • 每个任务运行在一个或多个 Container 中。

工作原理

应用提交

• 客户端向 ResourceManager 提交一个应用请求。
• ResourceManager 启动 ApplicationMaster 来管理该应用。

资源分配

• ApplicationMaster 与 ResourceManager 协商资源需求。
• ResourceManager 根据当前的资源调度策略分配容器。

任务执行

• ApplicationMaster 请求 NodeManager 启动 Container 并运行任务。
• NodeManager 在分配的容器中执行任务，并将状态返回给 ApplicationMaster。

任务完成

• ApplicationMaster 汇总任务执行结果并向 ResourceManager 汇报应用完成状态。

Serverless Computing

FaaS, 无服务器计算是一种云计算架构，指的是用户在开发和部署应用时无需管理底层服务器或基础设施，云服务提供商会自动分配、运行和维护计算资源。尽管名字叫“无服务器”，但实际上服务器依然存在，只是这些服务器被云服务提供商所管理，用户无需直接接触或配置它们。

Donate