01背包题解

完全背包题解

二维写法时两种背包问题核心代码的区别:



可以看出,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]);

最新文章

  1. javaWeb高级编程(1)
  2. TOMCAT运行一段时间后网页无响应或连不上,TOMCAT无错误日志
  3. Java mac 上编写Java代码
  4. poj3180 强连通
  5. ASP.NET Core 源码阅读笔记(5) ---Microsoft.AspNetCore.Routing路由
  6. POJ 2299 Ultra-QuickSort(线段树入门)
  7. 17_JSP_入门
  8. 玩转Web之servlet(二)---servlet常见错误
  9. js检测对象中是否存在某个属性
  10. &lt;context:annotation-config/&gt;
  11. uploadify在IE6下的问题
  12. 2.css字体单位
  13. 一步一步学J2SE-HashMap的实现原理
  14. Mybatis基本用法--上
  15. SpringMVC 框架系列之初识与入门实例
  16. python slenium 中CSS定位
  17. Windows NT 的历史
  18. 【做题】arc080_f-Prime Flip——转换、数论及匹配
  19. mysql中查看视图的元数据?
  20. Cocoa 集合类型:NSPointerArray,NSMapTable,NSHashTable

热门文章

  1. 动态构造LINQ表达式导致EFCore内存泄漏
  2. echarts柱状图快速上手笔记地址
  3. android9.0之后wifi热点原生接口开发示例
  4. docker中搭建Ubuntu:16.04+python3.6+django环境
  5. docker compose设置不同容器间通信
  6. 《Rust权威指南》学习笔记——8.通用集合类型
  7. uniapp for显示数据改变时,绑定的list值同时改变
  8. zerotier的planet服务器(根服务器)-搭建教程
  9. SecureCRT保存日志
  10. 【Python】容器:列表(list)/字典(dict)/元组(tuple)/集合(set)