C语言动态规划解决0-1背包问题

这篇具有很好参考价值的文章主要介绍了C语言动态规划解决0-1背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(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 : b

int 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,价值也为0
                f[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。

 文章来源地址https://www.toymoban.com/news/detail-861383.html

到了这里,关于C语言动态规划解决0-1背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走,则如何选择可以使得收益最高? 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入: quad - n n n 个商品组成集合 O O O ,每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(19)
  • 算法分析与设计——动态规划求解01背包问题

    假设有四个物品,如下图,背包总容量为8,求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题,首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如, (4, 8)表示在背包容量为8的情况下,前四个物品的最

    2024年02月04日
    浏览(16)
  • 算法套路十四——动态规划之背包问题:01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解,可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍:https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品,第i个物品的体积为w[i],价值为v[i],每个物品至多选一个, 求体积和不超过capacity时的最大价值和,其中i从

    2024年02月10日
    浏览(14)
  • C++算法初级11——01背包问题(动态规划2)

    辰辰采药 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时

    2024年02月02日
    浏览(12)
  • 动态规划——使用python解决01背包问题

    目录 什么是01背包问题? 题目: 输入格式: 输出格式: 代码实现: 代码执行示例: 代码解析:         01背包问题是一个经典的组合优化问题,通常用于描述如下情境:假设有一个背包,它能够承受一定的重量上限(即背包容量),同时有一组物品,每件物品有自己的重

    2024年02月03日
    浏览(17)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(14)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(16)
  • 01背包问题三种解决(贪心动态规划分支限界)

    一、实验目的 1、深入理解背包相关问题。 2、能正确设计相应的算法,解决实际问题。   3、掌握算法时间复杂度分析。 二、实验要求 用3种方法求解0-1背包问题(贪心算法、 动态规划、分支限界法 ),获得精确最优解或近似最优解均可。 通过一个规模较大的实例比较不同

    2024年02月02日
    浏览(25)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(20)
  • 力扣算法刷题Day42|动态规划:01背包问题 分割等和子集

    力扣题目:01背包问题(二维数组) 刷题时长:参考题解 解题方法:动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路:两层for循环,第一层i遍历物品,第二层j枚举背包容量以内所有值 确定dp数组及下标的含义:dp[i][j] 表示从下标

    2024年02月13日
    浏览(14)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包