动态规划

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度, 因此它比回溯法、暴力法等要快许多。

状态和状态转移方程

例子:01背包问题
有 n 个价值和重量分别为 v[i] 和 w[i] 的物品和一个容量为 m 的背包,要从中选出总重量不超过 m 的物品放入背包,问所有方案中价值总和的最大值。

输入

n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
w=5

输出

7(选择0,1,3号物品)

状态: dp[i][j] 表示考虑前 i 个物品,背包容量为 j 时的最大价值
初始: dp[n][j] = 0
状态转移方程:

状态转移方程

图解
int dp[N][N];
void solve(){
    for (int i=n-1;i>=0;i--){
        for(int j=0;j

本博客所有内容采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可

转载文章请注明:动态规划 - https://blog.i-ll.cc/archives/73

分类: Coding

Vectors

Vectors

不知所措,才是人生。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

我不是机器人*