背包基本模型

  1. 每个物品只有一个: 0/1背包
    \(f[i][j]=max\{ f[i-1][j],f[i-1][j-V_i]+W_i \}\)

有n个数 构成整数m的方案数

\(f[i][j]=f[i-1][j]+f[i-1][j-a_i]\)

  1. 每个物品有无限个: 完全背包
    \(f[i][j]=max\{ f[i-1][j],f[i][j-V_i]+W_i\}\)

N的正整数划分方案数
\(f[i][j]=f[i-1][j]+f[i][j-i]\)

  1. 每个物品有k个: 多重背包

  2. 把物品分组,每组最多选一个:分组背包
    \(f[i][j]=max{f[i-1][k],f[i-1][j-V_{i,k}]+W_{i,k}}\)

推荐这些文章:

CF-1354 E. Graph Coloring(二分图,背包,背包方案输出)

E. Graph Coloring
链接
n个点m条边的无向图,不保证联通,给每个点标号1,2,3。1号点个数n1,2号点个数n2,3号点个数n3。且每条边的两点,标号之差绝对值为1。如果有合法方案,需输出方案。
考虑每个联通子图,2只可以和1或者3连边,1只能和2连边,3只能和2连边,那么将1,3归为一堆,2归为一堆。每一堆内不存在边,构成一个独立点集,那么很明显是一个二分图,每次DFS可以找到二分图两部点的个数,如果存在奇环那么直接输出NO
对于每个联通子图,一个二分图,假设左部有 x 个点,右部有y个点,那么可以给x个点标2号,或者给 y 个点标2号。问最后能否刚好凑够 n2 个2号点...

三类基础的背包问题

背包问题
最基础的背包问题包含以下三个子问题:

0-1背包问题:N个物品和一个容量为C的背包,第i件物品消耗的容量为\(C_i\),价值是\(W_i\),求放入哪些物品可以使得总价值\(V\)最大
完全背包问题:有N种物品和一个容量为C的背包,每种物品都有无限件可用,第i件物品消耗的容量为\(C_i\),价值为\(W_i\),求解放入哪些物品可以使得背包中总价值\(V\)最大
多重背包问题:有N种物品和一个容量为C的背包,第i种物品最多有\(M_i\)件可用,每件物品消耗的容量为\(C_i\),价值为\(W_i\),求解入哪些物品可以使得背包中总价值\(V\)最大。

这三种问题的相同之处...

AcWing 算法基础课 动态规划

1、背包问题
  (1)01背包
  每件物品仅用一次 
  可以做空间优化
  dp[j]=max(dp[j],dp[j-v[i]]+w[i]);   
  0,1背包状态均是从前一循环的状态转移
  
  (2)完全背包
  每件物品可以用无限次
  dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  
  完全背包的状态可以从当前循环的状态转移,进行优化
  
 
 
 
 
 
  (3)多重背包
  每件物品有不同的数量限制
  可以对物品的数量限制进行拆分(1~2^k+c),从而转化为01背包问题
  
  也...

acwing-9. 分组背包问题

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。
接下来有 NN 组数据:

每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;

输出格式
输出一个整数,表示最大价值。
...

0~1背包 —— 动态规划

背包 —— 动态规划

问题描述:
给定n个物品和一背包。物品i的体积vi,其价值为wi,背包的最大容量为V。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

动态规划解法:
设F[i][j]表示只看前i个物品,总体积是j的情况下,总价值是多少
result = max(F[n][0~V])
现在开始逐个求F[i][j]:
对于F[i][j]而言一共存在两种情况,即选择当前第i个物品和不选择当前的第i个物品。故有以下 :

不选择第i个物品时,F[i][j] = F[i - 1][j]
选择第i个物品时,F[i][j] = F[i - 1][j - v[i]] + w[i]...

完全背包问题——动态规划

完全背包问题

问题描述:
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

动态规划解法:
设F[i][j]表示只看前i个物品,总体积是j的情况下,总价值是多少(与0~1背包表示意义一样)。先做出如下推导:
在计算状态i,j的值F[i][j]时,即在体积不超过j的情况下选择第i件物品时,除了要考虑前一状态F[i-1][j](在j的情况下只考虑前i-1件物品)外,还要考虑放置1件i物品、放置2件i物品·····放置k件i物品、直至放满...

文章标题:背包基本模型
文章链接:https://www.dianjilingqu.com/51327.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>