昨天小小总结了01背包：01背包 不足之处还望多提意见~噶呜~
今天来总结一下完全背包：
完全背包：
基本思路：类似于01背包，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，策略已经不是取与不取两种，而是取0件，取1件，..等很多种，如果仍按01背包的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，仍可按照每种物品的不同策略写出状态转移方程，like this:f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i])；
for i← to N
do for j← to V
do for k← to j/C[i]
if(j >= k*C[i])
then F[i][k] ← max(F[i][k],F[i-][j-k*C[i]]+k*W[i])
return F[N][V]
一个简单的优化：
若两件物品i,j满足c[i]<=c[j]&&w[i]>=w[j],则将物品j去掉不用考虑。 这个筛选过程如下：先找出体积大于背包的物品直接筛掉一部分（也可能一种都筛不掉）复杂度O(N)。利用计数排序思想对剩下的物品体积进行排序，同时筛选出同体积且价值最大的物品留下，其余的都筛掉（这也可能一件都筛不掉）复杂度O(V)。整个过程时间复杂度为O(N+V)
转化成01背包问题求解：
因为同种物品可以多次选取，那么第i种物品最多可以选取V/C[i]件价值不变的物品，然后就转化为01背包问题。整个过程的时间复杂度并未减少。如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品，其中满足C[i]×2k≤V。那么在求状态F[i][j]时复杂度就变为O(log2(V/C[i]))。整个时间复杂度就变为O(NVlog2(V/C[i]))
时间复杂度优化为O(NV)的算法：
这个算法使用一维数组：
for i:1 to N
do for v:0 to V
do f[v]=max{f[v],f[v-cost]+weight}
你会发现这个伪代码和01背包的伪代码只有v循环次序不同,为什么01背包要按照V=v~0来循环呢？这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来，这正是为了每件物品只选一次保证在考虑“选入第i件物品”这件策略时依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]，而现在完全背包的特点是每件物品可选无数件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i件物品的子结果：f[i][v-c[i]].
值得一提：
上面伪代码的两层for循环的次序可以颠倒，这个结论可能回来来算法时间常数上的优化。
总结：完全背包也是相当基础的背包问题，有上述两个状态转移方程。吾不才，希望多提意见~噶呜~
随机推荐
-
多重背包问题：悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（HDU 2191）(二进制优化)
悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 HDU 2191 一道裸的多重背包问题: #include<iostream> #include<algorithm> #i ...
-
OracleOraDb10g_home1TNSListener无法启动
1:“本地计算机上的OracleOraDb10g_home1TNSListener服务启动后停止.某些服务在未由其他服务或程序使用时将自动停止.” 解决办法:动态ip,服务 OracleOraDb10 ...
-
var_export函数的使用方法
var_export() 函数返回关于传递给该函数的变量的结构信息,它和 var_dump() 类似,不同的是其返回的表示是合法的 PHP 代码.var_export必须返回合法的php代码, 也就是 ...
-
栈的java实现和栈的应用
[例子和习题出自数据结构(严蔚敏版), 本人使用java进行实现. 转载请注明作者和出处, 如有谬误, 欢迎在评论中指正. ] 栈的实现 栈是一种先进后出的数据结构, 首先定义了栈需要实现的接口: ...
-
2018.12.05 codeforces 948C. Producing Snow（堆）
传送门 维护一个堆. 每次先算出一个都不弹掉的总贡献. 然后把要弹掉的弹掉,并减去它们对应的贡献. 代码: #include<bits/stdc++.h> #define ri regis ...
-
使用 ipmitool 实现远程管理Dell 系列服务器
IBM 文档: http://www.ibm.com/developerworks/cn/linux/l-ipmi/index.html ipmi命令收集: http://hi.baidu ...
-
初识Nosql
ref:http://www.runoob.com/mongodb/nosql.html https://blog.csdn.net/testcs_dn/article/details/512258 ...
-
OSGI企业应用开发（十二）OSGI Web应用开发（一）
前面文章中介绍了如何在OSGI应用中整合Spring和Mybatis框架,本篇文章开始介绍如何使用OSGI技术开发Web应用.对于传统的Java EE应用,应用中涉及到的Web元素无非就是Servle ...
-
easyUi 的DataGrid的绑定
html代码: @{ ViewBag.Title = "Index"; Layout = "~/Views/Shared/_Index_Layout.cshtml&quo ...
-
Go语言之进阶篇文件传输
一.文件传输 1.文件传输原理 2.文件传输 示例: 发送方: send_file.go package main import ( "fmt" "io" &q ...