01背包&完全背包二维写法的对比,进而理解一维优化后的正逆序
2024-09-08 17:10:32
二维写法时两种背包问题核心代码的区别:
可以看出,01背包用的是上一层的数据,完全背包用的是当前层的数据
所以优化为一维时,
01背包需逆序
for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完全背包需正序
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
最新文章
- javaWeb高级编程(1)
- TOMCAT运行一段时间后网页无响应或连不上,TOMCAT无错误日志
- Java mac 上编写Java代码
- poj3180 强连通
- ASP.NET Core 源码阅读笔记(5) ---Microsoft.AspNetCore.Routing路由
- POJ 2299 Ultra-QuickSort(线段树入门)
- 17_JSP_入门
- 玩转Web之servlet(二)---servlet常见错误
- js检测对象中是否存在某个属性
- <;context:annotation-config/>;
- uploadify在IE6下的问题
- 2.css字体单位
- 一步一步学J2SE-HashMap的实现原理
- Mybatis基本用法--上
- SpringMVC 框架系列之初识与入门实例
- python slenium 中CSS定位
- Windows NT 的历史
- 【做题】arc080_f-Prime Flip——转换、数论及匹配
- mysql中查看视图的元数据?
- Cocoa 集合类型:NSPointerArray,NSMapTable,NSHashTable
热门文章
- 动态构造LINQ表达式导致EFCore内存泄漏
- echarts柱状图快速上手笔记地址
- android9.0之后wifi热点原生接口开发示例
- docker中搭建Ubuntu:16.04+python3.6+django环境
- docker compose设置不同容器间通信
- 《Rust权威指南》学习笔记——8.通用集合类型
- uniapp for显示数据改变时,绑定的list值同时改变
- zerotier的planet服务器(根服务器)-搭建教程
- SecureCRT保存日志
- 【Python】容器:列表(list)/字典(dict)/元组(tuple)/集合(set)