0-1背包问题回溯法代码

全栈程序员-站长 • 2026年3月26日下午8:04 • 未分类 • 阅读 2

0-1背包问题回溯法代码include iostream usingnamespa intn intc intv 100 intw 100 intcw 0 intcp 0 intbestp 0 0 intput 100 intx 100 voidbacktrac inti intbound inti if i gt n for intj 1 j amp l iostream

#include  
     using namespace std; int n; int c; int v[100]; int w[100]; int cw = 0; int cp = 0; int bestp = 0.0; int put[100]; int x[100]; void backtrack(int i) { 
    int bound(int i); if(i>n) { 
    for(int j=1;j<=n;j++) put[j]=x[j]; bestp = cp; return; } if(cw+w[i]<=c) { 
    cw+=w[i]; cp+=v[i]; x[i]=1; backtrack(i+1); cw-=w[i]; cp-=v[i]; x[i]=0; } if(bound(i+1)>bestp){ 
    backtrack(i+1); } } int bound(int i) { 
    int leftw= c-cw; int b = cp; while(i<=n && w[i]<=leftw) { 
    leftw-=w[i]; b+=v[i]; i++; } if(i<=n) b+=v[i]*leftw/w[i]; return b; } int main() { 
    int i; scanf("%d %d",&c,&n); for(i=1;i<=n;i++){ 
    scanf("%d",&w[i]); } for(i=1;i<=n;i++){ 
    scanf("%d",&v[i]); } backtrack(1); printf("%d\n",bestp); for(i=1;i<=n;i++) { 
    cout<<put[i]<<" "; } return 0; }

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/177203.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

磁盘分区、格式化、挂载（fdisk mkfs partprobe）

上一篇 2026年3月26日下午8:03

java sdk 安装_Java SDK下载安装环境配置+AndroidKiller配置教程

下一篇 2026年3月26日下午8:04

micropython教程(Python集成开发环境)

本文旨在通过一个简单的demo，介绍基于Python3、PyQT5的环境下开发桌面应用程序的一种方案，当然开发Python的桌面应用程序不止是PyQT这一种方案，还可以使用Python自带的Tkinter来实现。本文目录：1.安装依赖环境2.安装Eric63.配置Eric4.创建窗口应用4.1创建窗体UI4.2实现代码逻辑参考资料：1.安装依赖环境Eric6官网：htt…

全栈程序员-站长
2022年4月17日
109
oracle vm virtualbox 卸载

oracle vm virtualbox 卸载为了学习 docker 下载安装了 DockerToolbo 18 03 0 ce exe 这个版本的工具出现了三个工具学习完成后想卸载了 dockerQuick 和 Kitemactic 都卸载了就留下一个 VMvirtualBox 虚拟机怎么卸载都卸载不了使用了删除注册表腾讯管家卸载等方法都卸载不了最后只能用很暴力的方法下载了个 WindowsInsta

全栈程序员-站长
2026年3月17日
2
MySQL按字符串hash分区_mysql分区理论「建议收藏」

MySQL按字符串hash分区_mysql分区理论「建议收藏」查看mysql安装的引擎mysql>showengines;查看mysql安装的插件(这里用于查看当前mysql是否支持partition)mysql>showplugins;不同分区对比分区类型优点缺点共性Range适合与日期类型，支持复合分区有限的分区一般只针对某一列List适合与有固定取值的列，支持复合分区有限的分区，插入记录在这…

全栈程序员-站长
2022年5月4日
274
基于H5+js开发一款音乐播放器

基于H5+js开发一款音乐播放器前言：当下音乐播放器不胜其数，为了更好的掌握一些东西，我们来自己制作一个音乐播放器。文章目录：一.开发环境：二.页面视图：1.主文件入口（首页）：2.音乐播放界面：三.功能实现（1）、index.html：（2）、播放音乐（music.html）：（3）、样式文件（index.css）：四.项目地址：一.开发环境：开发工具：HbuliderX；框架：Vant，Mui，Vue后端：Node二.页面视图：正常情况下我们的开发都会有构思图以及模块规划等过程，我们先来看看大致的页面构图：1

全栈程序员-站长
2022年6月29日
30
pycharm调试如何返回上一步_庞大的DCS系统是如何一步一步调试成功的？

pycharm调试如何返回上一步_庞大的DCS系统是如何一步一步调试成功的？一键获取技术资料现代煤化工政策汇编及解读 2020 版煤制烯烃产业研究报告 2020 版煤制油产业研究报告 2020 版煤制天然气产业研究报告 2020 版煤制乙二醇产业研究报告 2020 版煤制乙醇产业研究报告 2020 版煤制芳烃产业研究报告 2020 版中国煤化工战略规划报告山西篇内蒙古篇陕西篇咨询微信加时请注明报告点蓝色的字

全栈程序员-站长
2026年3月26日
2
python显示当前日期时间_python获取当前日期和时间的方法

python显示当前日期时间_python获取当前日期和时间的方法本文实例讲述了 python 获取当前日期和时间的方法分享给大家供大家参考具体如下 importdateti Getadatetime datetime datetime now Generalfunct Year d now yearprint Month d now monthprint Day d

全栈程序员-站长
2026年3月19日
1

发表回复

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