背包问题rust实现

2020-06-15 本文已影响0人 Jesse_996

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 {
    zoro_one_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 个物品的物品组，就可以直接应用分组背包的算法解决问题了

 1  /*
 2 即物品间存在依赖，比如i依赖于j，表示若选物品i，则必须选物品j
 3 <http://acm.hdu.edu.cn/showproblem.php?pid=3449>
 4 有很多个箱子，想买箱子中的物品必须先买下箱子，典型的依赖背包
 5 将不依赖其他物品的物品称为主件，依赖其他物品的物品称为附件
 6 我们有n个箱子，箱子里面的物品个数为cnt[i]
 7 那么箱子称为主件，箱子里面的物品称为附件
 8 那么考虑一个主件和它附件的集合，那么有2^n+1种策略，每种策略都是互斥的。所以它是分组背包问题。
 9 但是不能像一般的分组背包那样处理，因为组内有2^n+1种。
10 但是考虑到费用相同时，只选择价值最大的。所以可以对组内的附件进行01背包，得到费用依次为v-c[i]...0的最大价值
11 dp2[v-c[i]...0]
12 
13 */
14 #include <stdio.h>
15 #include <string.h>
16 int dp[100000+10],dp2[100000+10];
17 int box[55],cnt[55],price[55][11],value[55][11];
18 inline int max(const int &a, const int &b)
19 {
20     return a < b ? b : a;
21 }
22 int main()
23 {
24     int n,v,i,j,k;
25     while(scanf("%d%d",&n,&v)!=EOF)
26     {
27         memset(dp,0,sizeof(dp));
28         for(i=1; i<=n; ++i)
29         {
30             scanf("%d%d",&box[i],&cnt[i]);
31             memcpy(dp2,dp,sizeof(dp));
32             for(j=1; j<=cnt[i]; ++j)
33             {
34                 scanf("%d%d",&price[i][j],&value[i][j]);
35                 for(k=v-box[i]; k>=price[i][j]; --k)//附件进行01背包，每个dp2[k]对于组内的一种策略
36                     dp2[k] = max(dp2[k],dp2[k-price[i][j]]+value[i][j]);
37             }
38             for(k=box[i];k<=v; ++k)
39                 dp[k] = max(dp[k],dp2[k-box[i]]);//当容量为k时，取第i组的物品时得到的最大值和不取比较哪个大
40         }
41         printf("%d\\n",dp[v]);
42     }
43     return 0;
44 }

参考：
男人八题之多重背包问题
 背包问题总结（下）