动态规划-0-1背包问题

动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，由美国数学家 Bellman 等人在1957年提出，用于研究多阶段决策过程的优化问题。

[toc]

动态规划适合的问题（最优解）

动态规划法适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，这些问题必须满足最优化原理和子问题的“无后向型”。

动态规划的基本步骤

一般需要四个步骤;

st=>start: 定义最优子问题
e=>end: 确定边界条件
op1=>operation: 定义状态
op2=>operation: 定义决策和状态转换方程

st->op1->op2->e

0-1背包问题

有一个背包,承载量为 C,现有 n 个物品,其中物品 i (0< i <=n) 重量为 w_i,价值为p_i, 现在从 n 个物品里选择一个或多个装入背包,要求在物品总重量不超过 C 的前提下,所装入的物品价值最高.

1.定义最优子问题

每选择一个物品就可以看做一个阶段,其子问题就可以定义成每次向包里装入一个物品,直到超过背包最大容量为止.

2.定义状态

在满足"无后向性"要求下,定义问题的状态: s[i, j] 将第 i 件物品装入容量为 j 的包里所能获得的最大价值.

3.定义决策和状态转换方程

决策:判断装入第 i 件物品的总价值和不装入第 i 件物品的总价值哪个更大.
如果不装入第 i 件物品,则背包内物品的价值仍然是 s[i-1, j];
如果装入第 i 件物品,则背包内物品的价值就是 s[i-1, j-w_i]+p_i.
状态转换方程: $s[i, j] = max(s[i-1, j], s[i-1, j-w_i]+p_i)$

4.确定边界条件

边界条件就是没有装入任何物品的状态: $s[0, j] = 0$

5.递归写法

#include <iostream>
#include <algorithm>

using namespace std;

int q[6] = {0,3, 6, 5, 4, 6};   // 价值
int t[6] = {0,2, 4, 6, 5, 2};   // 重量
int V = 2;                      // 背包容量

int func(int i, int V);         // i 个物品, 背包容量 V
    
int main(int argc, char *argv[]) {
    
    int highest = func(5, V);
    cout << "最高价值：" << highest << endl;
    
    return 0;
}

int func(int i, int V){
    if(i == 0 || V == 0) {
        return 0;
    }else if (V>=t[i]){
        return max(func(i-1, V), func(i-1, V-t[i])+q[i]);
    }else{
        return func(i-1, V);
    }
}

6.状态表(备忘录)写法

#include <iostream>

using namespace std;

int q[6] = {0,3, 6, 5, 4, 6};   // 价值
int t[6] = {0,2, 4, 6, 5, 2};   // 重量
int V = 10;                     // 背包容量

int main(int argc, char *argv[]) {
    
    int f[6][V+1];                  // 状态表
    
    // 初始化边界条件
    for (int i = 0; i < 6; i++){
        f[i][0] = 0;
        f[0][i] = 0;
    }
    for (int i = 1; i < 6; i++){
        for (int j = 1; j < V+1; j++){
            if(j >= t[i]){
                f[i][j] = max(f[i-1][j], f[i-1][j-t[i]]+q[i]);
            }else{
                f[i][j] = f[i-1][j];
            }
        }
    }
    // 打印状态表
    for (int i = 0; i < 6; i++){
        for (int j = 0; j < V+1; j++){
        cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}