网站备案主办单位性质,张家港做网站收费标准,智能建站的优势和不足,建设银行查询余额进什么网站动态规划#xff08;Dynamic Programming#xff0c;简称DP#xff09;是一种在数学、计算机科学和经济学中使用的#xff0c;通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题#xff0c;它能够将问题…动态规划Dynamic Programming简称DP是一种在数学、计算机科学和经济学中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题它能够将问题分解为相互独立的子问题并将子问题的解存储起来以便下次需要时直接使用从而减少计算量提高效率。最经典的例子就是0-1背包问题。
0-1背包问题描述给定一组物品每种物品都有自己的重量和价值在限定的总重量内选取若干种物品使得物品的总价值最大。其中每种物品只能选择一次或不选择。
基本思路
用子问题定义状态f[i][c] 表示前 i 件物品放入一个容量为 c 的背包可以获得的最大价值。第 i 件物品的重量是 wi价值是 vi则其状态转移方程是
f[i][c] max(f[i-1][c], f[i-1][c-wi] vi)
这个方程非常重要基本上所有跟背包相关的问题的方程都是由它衍生出来的。分析子问题“将前 i 件物品放入容量为 c 的背包中”考虑第 i 件物品放或不放入背包可以转化为一个只牵扯前 i-1 件物品的问题如果不放第 i 件物品那么问题就转化为“前 i-1 件物品放入容量为 c 的背包中”价值为 f[i-1][c]如果放第 i 件物品那么问题就转化为“前 i-1 件物品放入剩下的容量为 c-wi 的背包中”此时能获得的最大价值就是 f[i-1][c-wi] 再加上通过放入第 i 件物品获得的价值 vi。所以按照这个方程递推完毕后最终的答案一定是 f[i][c]。 示例程序
#include stdio.h#define max(a, b) a b ? a : bint knapsack(int weights[], int values[], int capacity, int n) {// f[i][c] 表示在前i个物品中选择若干个物品放入容量为c的背包中所能获得的最大价值int f[n 1][capacity 1];for (int i 0; i n; i) {for (int c 0; c capacity; c) {if (i 0 || c 0) {// 前0个物品或者容量为0价值也为0f[i][c] 0;} else if (c weights[i-1]) {// i表示前i个物品所以第i个物品的重量是 weights[i-1]对应前面公式中的 wi// 遍历到当前容量c小于当前物品的重量无法放入该物品保持背包现状// 即上一轮遍历物品的循环中同样数量物品的最大价值所以是 f[i-1][c]f[i][c] f[i-1][c];} else {// i表示前i个物品所以第i个物品的价值是 values[i-1]对应前面公式中的 vi// 可以放入判断放入该物品是否能使背包中物品价值最大// 如果放入可能需要腾出背包中同样重量的物品所以是 f[i-1][c-weights[i-1]]// 然后 f[i-1][c-weights[i-1]] values[i-1] 得到放入该物品后的价值// 不放入该物品保持背包现状与放入该物品取两者中的最大值f[i][c] max(f[i-1][c], f[i-1][c - weights[i-1]] values[i-1]);}}}// 输出动态规划数组中的值显示规划过程用于分析理解for (int i 0; i n; i) {for (int c 0; c capacity; c) {printf(%d, f[i][c]);if (c capacity) {printf(, );}}printf(\n);}return f[n][capacity];
}int main() {// 物品重量int weights[] {2, 2, 1, 3};// 物品价值int values[] {4, 2, 3, 6};// 背包的容量限制int capacity 3;// 物品数量int n sizeof(values) / sizeof(values[0]);printf(最大价值: %d\n, knapsack(weights, values, capacity, n));return 0;
} 分析过程
程序输出如下
0, 0, 0, 0
0, 0, 4, 4
0, 0, 4, 4
0, 3, 4, 7
0, 3, 4, 7
最大价值: 7
上面输出的前5行是动态规划数组中的内容回顾一下程序中的这行注释内容f[i][c] 表示在前 i 个物品中选择若干个物品放入容量为 c 的背包中所能获得的最大价值。咱们的示例数据中一共有4个物品背包的容量为3所以数组的大小是5x4为什么维度比物品数和背包容量都大1请带着这个问题往下看。现在开始逐行分析数组中的数据
第1行不选择任何物品所以价值都为0。为方便阅读避免频繁上下滑动屏幕后续会复制所需查看的输出
0, 0, 0, 0
第2行选择前1个物品该物品重量为2价值为4。从0-3遍历背包容量依次尝试放入该物品遍历过程中容量为0都不能放入所以第1列数据永远为0。容量为1不能放入当前物品容量为2和3可以放入且是第1个物品可直接放入背包得到背包中物品的价值就是该物品的价值4。
0, 0, 0, 0
0, 0, 4, 4
第3行选择前2个物品问题转变为在前1个物品的基础上放入第2个物品。根据前面的子问题说明考虑第 i 件物品放或不放入背包可以转化为一个只牵扯前 i-1 件物品的问题如果不放第 i 件物品那么问题就转化为“前 i-1 件物品放入容量为 c 的背包中”价值为 f[i-1][c]如果放第 i 件物品那么问题就转化为“前 i-1 件物品放入剩下的容量为 c-wi 的背包中”此时能获得的最大价值就是 f[i-1][c-wi] 再加上通过放入第 i 件物品获得的价值 vi。第2个物品的重量为2价值为2。和前一个物品一样容量为2和3可以放入但背包剩余容量不够需要置换前面放入的物品。如果放入该物品置换出原价值为4的物品所能得到的价值为2小于背包中物品现有的价值4因此不放入该物品背包中物品价值仍为4。
0, 0, 0, 0
0, 0, 4, 4
0, 0, 4, 4
第4行选择前3个物品问题转变为在前2个物品的基础上放入第3个物品。第3个物品的重量为1价值为3。从0-3遍历背包容量容量为1时背包中没有物品直接放入背包中物品价值为该物品的价值3容量为2时由于已经放入物品价值为4该物品可以放入背包但背包剩余容量不够需要置换前面放入的物品置换后所能得到的价值为2小于背包中物品现有的价值4因此不放入该物品背包中物品价值仍为4容量为3时背包中有物品也有剩余容量根据前面的方程 f[i][c] max(f[i-1][c], f[i-1][c-wi] vi) 计算 f[3][3] max(f[2][3], f[2][3-1]3)即不放入该物品时的价值 f[2][3] 4与放入该物品时的价值 f[2][2]3 7因此放入该物品背包中物品价值最大为7。
0, 0, 0, 0
0, 0, 4, 4
0, 0, 4, 4
0, 3, 4, 7
第5行选择前4个物品问题转变为在前3个物品的基础上放入第4个物品。第4个物品的重量为3价值为6。从0-3遍历背包容量只有容量为3时可以放入该物品如果放入该物品置换出背包中容量为3的物品f[i-1][c-wi] vi f[3][0]6 6小于不放入该物品时背包中的物品价值7因此不放入该物品。
0, 0, 0, 0
0, 0, 4, 4
0, 0, 4, 4
0, 3, 4, 7
0, 3, 4, 7
最终的答案是 f[4][3]程序输出最大价值: 7。
