0-1 背包#
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗費的費用是 cost [i]， 价值是 value [i]。求解將哪些物品裝入背包可使價值總和最大
//初始化
let v = 2;//背包體積
let n = 4;//物品個數,必須等於cost和value的長度
let cost = vec![1, 2, 3, 4];//物品花費
let value = vec![1, 3, 5, 7];//物品價值
let mut f = vec![0; v + 1];
// 0 <= i < n
for i in 0..n {
zoro_one_pack(&mut f, cost[i], value[i], v);
}
//最後價值總和最大的值就是f[v]
fn zoro_one_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
for j in (cost..=v).rev() {
f[j] = std::cmp::max(f[j], f[j - cost] + value);
}
}
注意：
如果題目要求 恰好裝滿背包 , 則除了f[0]設為 0，其餘都設為 $-∞$，如果不要求恰好裝滿，則f全初始化為 0。
一個常數優化#
//伪代码
for i in 0..n {
for j in (cpm::max(cost[i],v-(cost[i]+..+cost[n-1]))..=v).rev() {
f[j] = std::cmp::max(f[j], f[j - cost[i]] + value[i]);
}
}
完全背包#
有
N種物品和一個容量為V的背包，每種物品都有無限件可用。放入第 i 種物品的費用是cost[i]，價值是value[i]。求解：將哪些物品裝入背包，可使這些物品的耗費的費用總 和不超過背包容量，且價值總和最大
思路是轉化成0-1 背包：將一種物品拆成多件只能選 0 件或 1 件的 01 背包中的物品。
//初始化
let v = 2;//背包體積
let n = 4;//物品個數,必須等於cost和value的長度
let cost = vec![1, 2, 3, 4];//物品花費
let value = vec![1, 3, 5, 7];//物品價值
let mut f = vec![0; v + 1];
// 0 <= i < n
for i in 0..n {
complete_pack(&mut f, cost[i], value[i], v);
}
//最後價值總和最大的值就是f[v]
fn complete_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
//就是將0-1背包中內層循環次序反轉
for j in cost..=v {
f[j] = std::cmp::max(f[j], f[j - cost] + value);
}
}
多重背包#
有
N種物品和一個容量為V的背包。第 i 種物品最多有M[i]件可用，每件耗費的空間是cost[i]，價值是value[i]。求解將哪些物品裝入背包可使這些物品的耗費的空間總和不超 過背包容量，且價值總和最大
fn multiple_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize, mut m: usize) {
if cost * m >= v {
complete_pack(f, cost, value, v);
return;
}
let mut k = 1;
while k < m {
zoro_one_pack(f, k * cost, k * value, v);
m -= k;
k *= 2;
}
zoro_one_pack(f, m * cost, m * value, v)
}
可行性問題#
當問題是 “每種有若干件的物品能否填滿給定容量的背包”，只須考慮填滿背包的可行性，不需考慮每件物品的價值時，多重背包問題同樣有 O (VN) 複雜度的算法
fn multiple_pack_ok() {
//也可以用硬幣模型來理解。v代表硬幣的總價值，n代表硬幣的種類，
//m是每個硬幣的數量，cost代表每種硬幣的價值
let v = 2;
let n = 4;
let cost = vec![5, 4, 9, 3];
let m = vec![2, 1, 4, 6];
let mut f = vec![-1; v + 1];
f[0] = 0;
for i in 0..n {
for j in 0..=v {
if f[j] >= 0 {
f[j] = m[i];
}
//else {
// f[j] = -1; 應為默認初始化就是-1
//}
}
if v < cost[i] {
break;
}
for j in 0..=(v - cost[i]) {
if f[j] >= 0 {
f[j + cost[i]] = std::cmp::max(f[j + cost[i]], f[j] - 1);
}
}
}
}
f[i][j]表示使用前i個物品，填充容量為j的背包，第i個物品最多能夠剩餘多少個，如果無法填充容量為j的背包，則值為-1
- 首先，
f[i - 1][j]代表前i - 1件物品凑面值j，如果其值大於等於0即狀態合法可以凑出j，就說明接下來不需要第i種硬幣就能凑出j，所以剩餘的硬幣數就是m[i]了。 - 如果
f[i - 1][j]小於0，說明前i-1種凑不出j。加上第i個硬幣可能面值太大，也可能正好，所以先取-1待定。 f[i][j + cost[i]] = std::cmp::max(f[i][j + cost[i]], f[i][j] - 1);如果能凑成j+cost[i], 那麼就把硬幣數量-1，如果不行，就維持-1的狀態。
然後把二維數組改為一維數組。
混合背包#
就是上面三種背包混合在一起
//伪代码：
for i in 0..n{
if i 是01背包{
zero_one_pack(..);
}else if i 是完全背包{
complete_pack(..);
}else if i 是多重背包{
multiple_pack(..);
}
}
二維背包#
對於每件物品，具有兩種不同的費用，選擇這件物品必須同時付出這兩種費用。對於每種費用都有一個可付出的最大值（背包容量）。問怎樣 選擇物品可以得到最大的價值。
設第 i 件物品所需的兩種費用分別為 Ci 和 Di。兩種費用可付出的最大值（也即兩種背包容量）分別為 V 和 U。物品的價值為 Wi
狀態轉移方程如下：
F[i, v, u] = max{F[i − 1, v, u], F[i − 1, v − Ci, u − Di] +Wi}
有時，“二維費用” 的條件是以這樣一種隱含的方式給出的：最多只能取 U 件物品。
這事實上相當於每件物品多了一種 “件數” 的費用，每個物品的件數費用均為 1，可以 付出的最大件數費用為 U
分組背包#
有 N 件物品和一個容量為 V 的背包。第 i 件物品的費用是 Ci，價值是 Wi。這些物品被劃分為 K 組，每組中的物品互相衝突，最多選一件。求解將哪些物品裝入背包 可使這些物品的費用總和不超過背包容量，且價值總和最大
設 F [k, v] 表示前 k 組物品花費費用 v 能取得的最大權值，則有：
F[k, v] = max{F[k − 1, v], F[k − 1, v − Ci] + Wi | item i ∈ group k}
fn group_pack(f: &mut Vec<usize>, v: usize, cost: &Vec<usize>, value: &Vec<usize>) {
let group = cost.len();
for j in (0..=v).rev() {
for k in 0..group {
if j < cost[k] {
break;
}
f[j] = cmp::max(f[j], f[j - cost[k]] + value[k]);
}
}
}
fn test_group() {
let v = 4;
let n = 3;
let cost = vec![vec![1, 2], vec![3, 4], vec![5, 6]]; //三組
let value = vec![vec![3, 2], vec![1, 5], vec![2, 4]]; //
let mut f = vec![0; v + 1];
for i in 0..n {
group_pack(&mut f, v, &cost[i], &value[i]);
}
dbg!(&f[v]);
}
有依賴的背包問題#
也就是說，物品 i 依賴於物品 j，表示若選物品 i，則必須選物品 j。
可以對主件 k 的 “附件集合” 先進行一次 01 背包，得到費用依次為 0. . .V − Ck 所有這些值時相應的最 大價值 Fk [0 . . . V − Ck]。那麼，這個主件及它的附件集合相當於 V − Ck + 1 個物品的 物品組，其中費用為 v 的物品的價值為 Fk [v −Ck] +Wk，v 的取值範圍是 Ck ≤ v ≤ V。 也就是說，原來指數級的策略中，有很多策略都是冗餘的，通過一次 01 背包後，將主件 k 及其附件轉化為 V −Ck + 1 個物品的物品組，就可以直接應用分組背包的算法解決問題了
/*
即物品間存在依賴，比如i依賴於j，表示若選物品i，則必須選物品j
http://acm.hdu.edu.cn/showproblem.php?pid=3449
有很多個箱子，想買箱子中的物品必須先買下箱子，典型的依賴背包
將不依賴其他物品的物品稱為主件，依賴其他物品的物品稱為附件
我們有n個箱子，箱子裡面的物品個數為cnt[i]
那麼箱子稱為主件，箱子裡面的物品稱為附件
那麼考慮一個主件和它附件的集合，那麼有2^n+1種策略，每種策略都是互斥的。所以它是分組背包問題。
但是不能像一般的分組背包那樣處理，因為組內有2^n+1種。
但是考慮到費用相同時，只選擇價值最大的。所以可以對組內的附件進行01背包，得到費用依次為v-c[i]...0的最大價值
dp2[v-c[i]...0]
*/
#include <stdio.h>
#include <string.h>
int dp[100000+10],dp2[100000+10];
int box[55],cnt[55],price[55][11],value[55][11];
inline int max(const int &a, const int &b)
{
return a < b ? b : a;
}
int main()
{
int n,v,i,j,k;
while(scanf("%d%d",&n,&v)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1; i<=n; ++i)
{
scanf("%d%d",&box[i],&cnt[i]);
memcpy(dp2,dp,sizeof(dp));
for(j=1; j<=cnt[i]; ++j)
{
scanf("%d%d",&price[i][j],&value[i][j]);
for(k=v-box[i]; k>=price[i][j]; --k)//附件進行01背包，每個dp2[k]對於組內的一種策略
dp2[k] = max(dp2[k],dp2[k-price[i][j]]+value[i][j]);
}
for(k=box[i];k<=v; ++k)
dp[k] = max(dp[k],dp2[k-box[i]]);//當容量為k時，取第i組的物品時得到的最大值和不取比較哪個大
}
printf("%d\n",dp[v]);
}
return 0;
}