蛮力法解决01背包问题-程序员宅基地

技术标签： 数据结构与算法  

蛮力法：设计算法求解背包问题，并编程实现。

背包问题: 

给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。

背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集。

实验：

编写程序，实现背包问题的蛮力算法。并针对以下两个实例，求出能装到背包中的价值最大的子集。要求输出：最优可行子集和该子集的最大价值。

代码实现：

#include <iostream>

int sum_v;//货物总价值
int sum_w;//货物总重量
int goodNum;//一共有多少货物
int ans;//背包中现有几个货物
int maxWeight;//背包的总容量
int r[100];//记录最后的选择的货物标号

using namespace std;
struct good
{
    int weight;
    int value;
    int flag;//记录该货物是否被挑选
}goods[100];
//更新序列，并返回最大
int record(int sum_v)
{
    int count_good = 0;
    r[0] = sum_v;
    for(int i = 1;i <= goodNum;i++)
    {
        if(goods[i].flag == 1)
        {
            r[++count_good] = i;
        }
    }
    return count_good;
}
void findMin(int x)
{
    if(sum_w > maxWeight)
    {
        return;
    }
    //最好在此处判断sun_v是否为最大，这样才不会有sum_w > maxWeight的情况
    if(sum_v > r[0])
    {
        ans = record(sum_v);
    }
    //注意此处循环的条件
    for(int i = x;i < goodNum;i++)
    {
        sum_w += goods[i].weight;
        sum_v += goods[i].value;
        goods[i].flag = 1;
        findMin(i + 1);
        sum_w -= goods[i].weight;
        sum_v -= goods[i].value;
        goods[i].flag = 0;
    }
}

int main()
{
    cin >> goodNum >> maxWeight;
    for(int i = 1;i <= goodNum;i++)
    {
        goods[i].flag = 0;
        cin >> goods[i].weight >> goods[i].value;
    }
    findMin(0);
    for(int i = 1;i <= ans;i++)
    {
        cout << r[i] << " ";
    }
    cout << "maxValue" << r[0] << endl;
    return 0;
}

第一行输入货物总个数和背包的总容量

10 60
23 20
15 14
8 7
20 18
7 5
10 11
9 10
16 15
21 19
13 12
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Geek_sun/article/details/82848705

智能推荐

已知num为无符号十进制整数，请写一非递归算法，该算法输出num对应的r进制的各位数字。要求算法中用到的栈采用线性链表存储结构(1＜r＜10)。-程序员宅基地

文章浏览阅读74次。思路：num%r得到末位r进制数，num/r得到num去掉末位r进制数后的数字。得到的末位r进制数采用头插法插入链表中，更新num的值，循环计算，直到num为0，最后输出链表。//重置，s指针与头指针指向同一处。//更新num的值，至num为0退出循环。//末位r进制数存入s数据域中。//头插法插入链表中(无头结点)//定义头指针为空，s指针。= NULL) //s不为空，输出链表，栈先入后出。

开始报名！CW32开发者扶持计划正式进行，将助力中国的大学教育及人才培养_cw32开发者扶持计划申请-程序员宅基地

文章浏览阅读176次。武汉芯源半导体积极参与推动中国的大学教育改革以及注重电子行业的人才培养，建立以企业为主体、市场为导向、产学研深度融合的技术创新体系。2023年3月，武汉芯源半导体开发者扶持计划正式开始进行，以打造更为丰富的CW32生态社区。_cw32开发者扶持计划申请

希捷硬盘开机不识别，进入系统后自动扫描硬件以识别显示_st2000dm001不认盘-程序员宅基地

文章浏览阅读5.7k次。2014年底买的一块2TB希捷机械硬盘ST2000DM001-1ER164，用了两年更换了主板、CPU等，后来出现开机不识别的情况，具体表现为：关机后开机，找不到硬盘，就进入BIOS了，只要在BIOS状态下待机半分钟左右再重启，硬盘就会出现。进入系统后，重启（这个过程中主板对硬盘始终处于供电状态），也不会出现不识别硬盘的现象。就好像是硬盘或主板上某个电容坏了一样，刚开始给硬盘通电的N秒钟内电容未能..._st2000dm001不认盘

ADO.NET包含主要对象以及其作用-程序员宅基地

文章浏览阅读1.5k次。ADO.NET的数据源不单单是DB，也可以是XML、ExcelADO.NET连接数据源有两种交互模式：连接模式和断开模式两个对应的组件：数据提供程序(数据提供者)&DataSetSqlConnectionStringBuilder——连接字符串Connection对象用于开启程序和数据库之间的连接public SqlConnection c..._列举ado.net在操作数据库时,常用的对象及作用

Android 自定义对话框不能铺满全屏_android dialog宽度不铺满-程序员宅基地

文章浏览阅读113次。【代码】Android 自定义对话框不能铺满全屏。_android dialog宽度不铺满

Redis的主从集群与哨兵模式_redis的主从和哨兵集群-程序员宅基地

文章浏览阅读331次。Redis的主从集群与哨兵模式Redis的主从模式全量同步增量同步Redis主从同步策略流程redis主从部署环境哨兵模式原理哨兵模式概述哨兵模式的作用哨兵模式项目部署Redis的主从模式1、Redis虽然读取写入的速度都特别快,但是也会产生读压力特别大的情况。2、为了分担读压力，Redis支持主从复制，保证主数据库的数据内容和从数据库的内容完全一致。3、Redis的主从结构可以采用一主多从或者级联结构，Redis主从复制可以根据是否是全量分为全量同步和增量同步。全量同步Redis全量复制一般发_redis的主从和哨兵集群

随便推点

mysql utf-8的作用_为什么不建议在MySQL中使用UTF-8-程序员宅基地

文章浏览阅读116次。作者：brightwang原文：https://www.jianshu.com/p/ab9aa8d4df7d最近我遇到了一个bug，我试着通过Rails在以“utf8”编码的MariaDB中保存一个UTF-8字符串，然后出现了一个离奇的错误：Incorrect string value: ‘😃 我用的是UTF-8编码的客户端，服务器也是UTF-8编码的，数据库也是，就连要保存的这个字符串“????..._mysql utf8的作用

MATLAB中对多张图片进行对比画图操作（包括RGB直方图、高斯＋USM锐化后的图、HSV空间分量图及均衡化后的图）_matlab图像比较-程序员宅基地

文章浏览阅读278次。毕业这么久了，最近闲来准备把毕设过程中的代码整理公开一下，所有代码其实都是网上找的，但都是经过调试能跑通的，希望对需要的人有用。PS：里边很多注释不讲什么意思了，能看懂的自然能看懂。_matlab图像比较

16.libgdx根据配置文件生成布局(未完)-程序员宅基地

文章浏览阅读73次。思路:　　screen分为普通和复杂两种,普通的功能大部分是页面跳转以及简单的crud数据,复杂的单独弄出来　　跳转普通的screen,直接根据配置文件调整设置<layouts> <loyout screenId="0" bg="bg_start" name="start" defaultWinId="" bgm="" remark=""> ..._libgdx ui 布局

playwright-python 处理Text input、Checkboxs 和 radio buttons（三）_playwright checkbox-程序员宅基地

文章浏览阅读3k次，点赞2次，收藏13次。playwright-python 处理Text input和Checkboxs 和 radio buttonsText input输入框输入元素，直接用fill方法即可，支持 ,,[contenteditable] 和<label>这些标签，如下代码：page.fill('#name', 'Peter');# 日期输入page.fill('#date', '2020-02-02')# 时间输入page.fill('#time', '13-15')# 本地日期时间输入p_playwright checkbox

windows10使用Cygwin64安装PHP Swoole扩展_win10 php 安装swoole-程序员宅基地

文章浏览阅读596次，点赞5次，收藏6次。这是我看到最最详细的安装说明文章了，必须要给赞！学习了，也配置了，成功的一批！真不知道还有什么可补充的了，在此做个推广，喜欢的小伙伴，走起！_win10 php 安装swoole

angular2里引入flexible.js（rem的布局）_angular 使用rem-程序员宅基地

文章浏览阅读1k次。今天想实现页面的自适应，本来用的是栅格，但效果不理想，就想起了rem布局。以前使用rem布局，都是在原生html里，还没在框架里使用过，百度没百度出来，就自己琢磨，不知道方法规范不规范，反正成功了，操作如下：1、下载flexible.js2、引入到angular项目里3、根据自己的需要修改细节3.1、在flexible.js里修改每份的像素，3.2、引入cssrem插件，在设置里设..._angular 使用rem

推荐文章

热门文章

相关标签