动态规划——背包问题(c语言)

动态规划——背包问题(c语言)/*背包问题:背包所能容纳重量为10;共五件商品,商品重量用数组m存储m[5]={2,2,6,5,4},每件商品的价值用数组n存储,n[5]={6,3,5,4,6};求背包所能装物品的最大价值。

大家好,又见面了,我是你们的朋友全栈君。

/*背包问题:
背包所能容纳重量为10;共五件商品,商品重量用数组m存储m[5]={2,2,6,5,4},
每件商品的价值用数组n存储,n[5]={6,3,5,4,6};求背包所能装物品的最大价值。
*/
#include<stdio.h>
#include<conio.h>
int main() {
    int m[5] = { 2,2,6,5,4 }, n[5] = { 6,3,5,4,6 };
    int flag[5] = { 0,0,0,0,0 };//符号标志位,表示地某个点是否装入背包,装入为1,未装入为0;
    int i, j, k;
    int c = 10, sum1 = 0, sum2 = 0;//sum1表示最终背包容纳的重量。sum2表示最终背包中容纳的最大价值的价值。
                                   //设一个二维数组,横坐标表示所装物品的标号,纵坐标表示背包所容纳的最大重量0~10;
    int mn[5][11];
    for (i = 4; i >= 0; i--) {//二维数组从下至上
        for (j = 0; j <= 10; j++) {
            if (i == 4) {
                if (m[i]>j)
                    mn[i][j] = 0;
                else
                    mn[i][j] = n[i];
            }
            else {
                if (m[i]>j) {
                    mn[i][j] = mn[i + 1][j];
                }
                else {
                    mn[i][j] = mn[i + 1][j]>mn[i + 1][j - m[i]] + n[i] ? mn[i + 1][j] : mn[i + 1][j - m[i]] + n[i];
                }
            }
        }
    }

    for (i = 0; i<5; i++) {
        if (mn[i][c] != mn[i + 1][c]) {//从二维数组上方开始,背包最大值c,mn[i][c]的值若与mn[i+1][c]的值不同,则m[i]未放入背包中(之前是自下往上放的)
            flag[i] = 1;
            c = c - m[i];//若放入背包,则背包可容纳总重量减少;
        }
        printf("%d ", flag[i]);
    }//输出所放入的物品序号

    for (i = 0; i<5; i++) {
        if (flag[i] == 1) {
            sum1 += m[i];
            sum2 += n[i];
        }
    }
    printf("\n背包容纳的重量为:%d 背包容纳的总价值为:%d", sum1, sum2);

    getch();
    return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/154547.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 游戏常用算法-洗牌算法

    游戏常用算法-洗牌算法洗牌算法是一个比较常见的面试题。一副扑克54张牌,有54!种排列方式。最佳的洗牌算法,应该能够等概率地生成这54!种结果中的一种

  • 遗传算法经典实例matlab代码_退火算法与遗传算法

    遗传算法经典实例matlab代码_退火算法与遗传算法经典遗传算法及简单实例(MATLAB)1.遗传算法简单介绍1.1理论基础1.2算法要点1.1编码1.2适应度函数1.3基本流程2.雪兔实例1.遗传算法简单介绍1.1理论基础整个算法的基础就是达尔文的生物进化论,“物竞天择,适者生存”这句话已经是常识了。雪兔的故事:东北那旮瘩,有群原始雪兔,刚从未知物种进化而来,五颜六色(表现型)漂亮极了,称之为I(0)。(注意:种群初始化)入夏了,雪兔们出来觅食,浅色兔在草地中无所遁形,被雪狐收割了一波(大批浅色+小批深色)。入冬了,雪

  • 论文外文文献怎么找_外文文献怎么翻译

    论文外文文献怎么找_外文文献怎么翻译论文参考文献的写作体现了作者对科学研究的态度和对文献作者的尊敬的优良品德,基于java网上购物论文英文的参考文献要怎么写呢?来看看学术参考网的小编整理的文献,希望给大家在写作当中带来帮助。基于java网上购物论文英文的参考文献:[1]刘鑫.基于JSP的网上购物系统研究与设计[D].北京:北京邮电大学,2013:42-43.[2]孔祥盛.MySQL数据库基础与实例教程[M].北京:人民邮电大学出版社…

  • VS2008简体中文正式版序列号

    VS2008简体中文正式版序列号VS2008简体中文正式版序列号1.VisualStudio2008ProfessionalEdition:XMQ2Y-4T3V6-XJ48Y-D3K2V-6C4WT2.VisualStud

  • 简述springboot自动配置_如何配制溶液

    简述springboot自动配置_如何配制溶液阅读收获:+1|type_1_2:理解SpringBoot自动配置原理SpringBoot是什么SpringBoot的诞生就是为了简化Spring中繁琐的XML配置,其本质依然还是Spring框架,使用SpringBoot之后可以不使用任何XML配置来启动一个服务,使得我们在使用微服务架构时可以更加快速的建立一个应用。简单来说就是SpringBoot其实不是什么新的框架,它默认配置了很多框架的使用方式。SpringBoot的特点 提供了固定的配置来简化配置…

  • 使用mongodb还需要redis吗_golang mongodb

    使用mongodb还需要redis吗_golang mongodbmongoDB;mongoVUE

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号