• 欢迎光临~

关于 完全背包

开发技术 开发技术 2022-09-28 次浏览

问题描述:

有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。第i件物品的体积是 w[i] ,价值是 v[i] 。求解将哪些物品装入背包可使价值总和最大。


问题特点:

每种物品有无限个,可以选择 i 物品的数量放入背包。


曲线救国:

将每种物品的无限个分成 k 组:

(虽然分成若干组来做,但 k 不能无限大,因为 i 物品有体积,k 个 i 物品的体积不能超过背包容量。)

1、去掉 k 个物品 i

2、求 Max ,dp[ i - 1 ][ j - k * w[i] ]

3、再加回来 k 个物品 i


状态转移方程:

dp[i][j] = max ( dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i] )


例题:https://www.acwing.com/problem/content/3/

程序员灯塔
转载请注明原文链接:关于 完全背包
喜欢 (0)