JZTXT

算法题总结-分组背包

发布时间 2023-06-11 16:29:10作者: 356a

原题
有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 Ci，价值是 Wi。这些
物品被划分为 K 组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包
可使这些物品的费用总和不超过背包容量，且价值总和最大。

由于截止目前，没有刷到对应的经典题目，以下以依赖背包的转化题目进行解析
https://www.cnblogs.com/dengliang356a/p/17473023.html
依赖背包的原始数据：

4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10

分组以后的策略：

100:300
400:2000
300:1500
1400:2800    2200:4400    2800:9800    3600:11400
500:1000
300:1500    1700:5700
500:1000    940:3200
1800:7200

分组挑选策略：

F_optimize = collections.defaultdict(int)
for groupIndex in range(len(strategy)):
    for volume in range(n+1,0,-1):
        for item in strategy[groupIndex]:
            if (volume-item.price)<0:
                continue
            F_optimize[volume] = max(F_optimize[volume],F_optimize[volume-item.price]+item.satisfaction)
            pass
        pass
    pass
print(F_optimize[n])