01背包的动态规划问题（包括代码C）

1. 动态编程的基本思想

动态编程算法通常用于解决具有某些最佳属性的问题. 基本思想是将要解决的问题分解为几个子问题，首先解决子问题，然后从这些子问题的解决方案中获得原始问题的解决方案. 与分治法不同，它适用于通过动态规划解决的问题，分解后获得的子问题通常彼此不独立. 如果使用分治法来解决这些问题，则通过分解获得的子问题的数目太大，并且某些子问题被重复计算多次. 如果我们可以保存已解决子问题的答案，并在需要时找到所需的答案，则可以避免大量重复计算并节省时间. 我们可以使用表格记录所有已解决子问题的答案. 无论将来是否使用该子问题，只要已经计算出该子问题，结果都将填入表格中. 这是动态编程方法的基本思想. 具体的动态编程算法是多种多样的，但是它们具有相同的表格填充形式. 分治法最大的不同在于它适用于通过动态编程解决的问题. 分解后获得的子问题通常不是彼此独立的（也就是说，下一个子阶段的解决方案基于上一个子阶段的解决方案，以供进一步解决）

2. 动态规划的应用场景

应用动态规划的问题必须符合优化原则，没有后遗症和重叠.

a. 优化原理（最佳子结构的性质）优化原理可以描述如下: 优化策略具有这样的属性: 无论过去的状态和决策如何，由先前决策形成的其余状态都将保留. 所有决策都必须构成最佳策略. 简而言之，优化策略的子策略始终是最佳的. 据说满足优化原理的问题也具有最佳的子结构属性.

b. 在将每个阶段按一定顺序排列而没有后效之后，对于给定的阶段状态，其前一阶段状态不能直接影响其将来的决策动态规划01背包问题c++，而只能影响当前的决策. 状态. 换句话说，每个状态都是过去历史的完整摘要. 这不是落后动态规划01背包问题c++，也没有后效应.

c. 子问题的重叠动态规划将原来的指数时间复杂度搜索算法改进为多项式时间复杂度算法. 关键是解决冗余，这是动态编程算法的基本目的. 动态编程本质上是一种交换时间的算法. 在实现过程中，它必须在生成过程中存储各种状态，因此其空间复杂度要高于其他算法.

为3.01背包问题建模: 如下所示

图片中abc的三个公式的详细分析: 公式a表示背包中负载为0的上一个项目与负载中没有背包的项目等于0. 类型b显示如果如果第一件物品的重量大于背包的容量，则通过加载前一件物品获得的最大值和通过加载第一件物品获得的最高价格是相同的，即，该物品不能加载到背包中. 公式c显示，如果第一件物品的重量小于背包的容量，则将出现两种情况: （1）如果将第一件物品装入背包，则背包物品的值等于负载第一项的容量-_背包的值加上第一项的值_； （2）如果没有将第一件物品装入背包，则该物品在背包中的值等于通过将第-1件物品装入具有该值的容量的背包而获得的值. 显然，两者中最有价值的是将前一件物品装入容量为背包的最佳解决方案.

4. 动态编程的时间效率为O（nc），其中n代表物品数量，c代表背包的容量. 空间的效率是用于存储二维数组的已占用空间的大小，为O（nc）.

5. 代码如下:

#include<stdio.h>
#include<cstdlib>
int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a, int b)
{
    if (a >= b)
        return a;
    else return b;
}
int KnapSack(int n, int w[], int v[], int x[], int C)
{
    int i, j;
    for (i = 0; i <= n; i++)
        V[i][0] = 0;
    for (j = 0; j <= C; j++)
        V[0][j] = 0;
    for (i = 0; i < n; i++){
        for (j = 0; j < C+1; j++){
            if (j<w[i])
                V[i][j] = V[i - 1][j];
            else
                V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
        }
    }
    j = C;
    for (i = n - 1; i >= 0; i--)
    {
        if (V[i][j]>V[i - 1][j])
        {
            x[i] = 1;
            j = j - w[i];
        }
        else
            x[i] = 0;
    }
    printf("选中的物品是:\n");
    for (i = 0; i<n; i++)
        printf("%d ", x[i]);
    printf("\n");
    for (int i = 0; i < n; i++){
        for (int j = 0; j < C+1; j++){
            printf("%d\t ", V[i][j]);
            if (j == C){
                printf("\n");
            }
        }
    }
    return V[n - 1][C];
}
int main()
{
    int s;//获得的最大价值
    int w[5] = {2,2,6,5,4};//物品的重量
    int v[5] = {6,3,5,4,6};//物品的价值
    int x[5];//物品的选取状态
    int n = 5;
    int C=10;//背包最大容量

    s = KnapSack(n, w, v, x, C);
    printf("最大物品价值为:\n");
    printf("%d\n", s);
    system("pause");
    return 0;
}

运行结果:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-202047-1.html