当前位置：首页 > article >正文

【算法设计与分析】实验4：动态规划—0/1背包问题

article 2025/2/1 15:44:05

一、实验目的

二、实验环境

三、实验内容

四、核心代码

五、记录与处理

六、思考与总结

七、完整报告和成果文件提取链接

一、实验目的

掌握动态规划求解问题的思想；针对不同的问题，会利用动态规划进行设计求解以及时间复杂度分析，并利用C/C++/ JAVA/Python等编程语言将算法转换为对应的程序上机运行（语言自选）。

理解0/1背包问题的目标函数及约束函数。能够根据动态规划思想，进行0/1背包最优子结构性质分析、子结构递归关系构建、编码实现子结构最优值求解以及最优解构造。

二、实验环境

1、机房电脑 Window7

2、Dev-C++/ Eclipse等

三、实验内容

实验要求：

①掌握动态规划求解问题的策略及思路；

动态规划往往用于求解最优化问题，它与分治法较为相似，都将问题切分成子问题进行处理，并且子问题存在重叠，且具有迭代递归关系，并且存在最优子结构特点——如果总问题是最优解，则所有子问题都是最优解。

同时动态规划通常采用自底向上的方式进行，迭代计算子问题、存储子问题的解，逐步求解更大规模的问题，直到求解出原问题。

动态规划主要包括两个要素：最优子结构和重叠子问题，最优子结构是问题能用动态规划求解的前提。

②基于动态规划算法设计求解0/1背包问题的求解；

通过指定n个物品对应的重量w以及价值v，指定当前背包容量C，通过动态规划求解当前可以达到的最大价值以及如何装可以达到该最大价值。将各子结构获取的最大价值，存放在M[i][j]数组中，将商品取或不取的结果，存放在X[i]数组中。

例如：背包容量C=23kg，各商品重量及价值如下：

商品序号	1	2	3	4	…..
重量	10kg	5kg	2kg	7kg	4kg
价值	80元	50元	10元	35元	24元

如何取得到最大价值M[i][j]？商品取或不取数组X[i]的取值？

1.找出最优问题特点；

若{y1,y2,y3,y4,y5}为容量C=23，n=5(商品1至于5)的问题的最优解y∈{0，1}

且{z2,z3,z4,z5}为容量C-y1w1,n=4 (商品2至5)问题的最优解，z∈{0，1}

则{z2,z3,z4,z5}一定等于{y2,y3,y4,y5}

所以得出结论：当(y1,y2……yn)是背包容量为C时的一组最优解；

那么 ( y2……yn)是背包容量为C-w1y1的最优解；

该问题满足最优子结构的特点，同时也包含多个重叠子问题，所以该问题可以采用动态规划算法求解。

2.定义递归关系；

要构造二维数组：m[i][j]表示当前子结构背包的最大价值。

考虑将i，i+1，…，n的商品，放入容量为j的背包中：可装入商品的最大价值为m(i,j)

根据每次取商品时的背包容量情况可得如下的递归关系：

(1) 当第i个物品的重量wi超过背包容量j时，第i个物品不能装入；有：

m[i][j]=m[i-1][j]

（2）当第i个物品的重量wi不超过背包容量j时，第i个物品可装入可不装入，则有：

m[i][j]=max( m[i-1][j] ，m[i-1][j-wi]+vi)

此时背包最大价值m[i][j]的递归关系为：

从m[i][j]的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2^n时，算法需要O(n2^n)计算时间。

优化：其中发现m数组的第一维没有实际用处，因为i最后都会等于物品数。于是可以对递归算法进行空间上的优化：把m换成一维数组，用f[j]表示背包容量为j的时候所能获得的最大价值。

递归表达式为：

③对上述算法进行时间复杂性分析，并输出程序运行时间及运行结果。

二维解法和一维解法的时间复杂度都是 O (nc)，但是一维解法的空间复杂度为 O (c)。

二维解法数据的存储得用到二维数组，空间开销大。所以可以把动态规划空间进行优化，使用一维数组使得空间效率从O(n*c)转化为O(c)，优化了空间，但优化后只能求出最优解，解的取舍过程在运行时已被破坏。所以可以根据自己的情况选择不同方案。

四、核心代码

 // 通过动态规划表反向推导出选择了哪些商品
    int j = c; // 从总容量c开始
    for (int i = m; i >= 1; i--) {
        if (j >= w[i] && dp[i][j] > dp[i-1][j]) {
            x[i] = 1; // 选择当前商品
            j -= w[i]; // 更新剩余容量
        } else {
            x[i] = 0; // 不选择当前商品
        }
    }
    
    cout << "输出m个商品的取舍方案："; // 输出商品选择方案
    for (int i = 1; i <= m; i++) // 遍历所有商品，输出选择状态（1表示选择，0表示不选择）
        cout << x[i] << " ";
    
    return 0;