+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-03(76)

2020-04(53)

2020-05(35)

2020-06(41)

2020-07(17)

动态规划中关于背包问题的一些整理

发布于2020-05-17 18:44     阅读(1066)     评论(0)     点赞(2)     收藏(1)


0-1背包

'基本01背包'
'''
这是最基础的背包问题:特点:一定容量,每个物品只有一件,在面临选择的时候可以选择放或者不放。
以f[i][j]表示前i件物品恰放进容量为j的背包可以获得的最大价值。状态转移方程:
f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])

可以对空间复杂度进行优化,用一维进行处理,可得到以下代码
'''
# 假设有10件物品,容量V = 50
n = 10
V = 50
w = list(range(n+1))
s = list(range(n+1))  # 记录w的前缀和
v = list(range(n+1))
f = list(range(V+1))
s[0] = 0
for i in range(1,n+1,1):
    w[i],v[i]=map(int,input("put w and v").split()) # 按空格分开输出
    s[i] = s[i-1]+w[i]
'''
一维做法
for i in range(1,n+1,1):
    for j in range(V,w[i]-1,-1):
        f[j] = max(f[j],f[j-w[i]]+v[i])'''
'''
一个常数优化 c 代码,减去了不必要的容量情况
# for (int i = 1; i <= n; i++) {
#     int bound = max(V - sum{w[i + 1]...w[n]}, w[i]);
#     for (int j = V; j >= bound, j--)
#         f[j] = max(f[j], f[j - w[i]] + v[i]);
# }
python代码:'''
for i in range(1,n+1):
    bound = int(max(w[i],V-(s[n]-s[i])))
    for j in range(V,bound-1,-1):
        f[j] = max(f[j],f[j-w[i]]+v[i])
print(f[V])

2.完全背包

''' 完全背包
与0-1背包的区别是任意一件物品有无限的数量
可反复装入背包,只要满足总价值最大就行
状态转移方程:
f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k∗w[i]<=j
'''
# 假设有10件物品,容量V = 50
n = 10
V = 50
w = list(range(n+1))
s = list(range(n+1))  # 记录w的前缀和
v = list(range(n+1))
f = list(range(V+1))
s[0] = 0
for i in range(1,n+1,1):
    w[i],v[i]=map(int,input("put w and v").split()) # 按空格分开输出
    s[i] = s[i-1]+w[i]
# 解法如同 0-1背包,但由于可以装一件一件物品多次,所以与0-1背包不同的是从下往上取,这样可以重复取多次
# 代码如下:
for i in range(1,n+1):
    for j in range(w[i],V+1):
        f[j]=max(f[j],f[j-w[i]]+v[i])
print(f[V])

3.多重背包

'''多重背包问题相当于是0-1背包的和完全背包的又一个扩展
与0-1背包不同的是它一件物品可能有多个,而与多重背包区别
的是它一件武平的数量也有限制
做法一:可对完全背包的方程进行改动即可
f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k<=p[i]
需要多加一层大小为p[i]的循环
做法二:转化为0-1背包,仍然考虑二进制的思想,将第i种物品分
成若干物品,每个物品的系数是2的指数倍,1,2,4,8,2^(k-1),p[i]-2^k+1.
种情况,且k是满足p[i]-2^k+1>0的最大整数。
例如13分为1,2,4,6 代码如下
for (int i = 1; i <= n; i++) {
    int num = min(p[i], V / w[i]);
    for (int k = 1; num > 0; k <<= 1) {
        if (k > num) k = num;
        num -= k;
        for (int j = V; j >= w[i] * k; j--)
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
    }
}
'''
for i in range(1,n+1):
    num = min(p[i],V/[i]);
    k = 1
    while(num):
        if k > num: k =num
        num-=k
        for j in range(V,w[i]-1,-1):
            f[j] = max(f[j],f[j-w[i]*k]+v[i]*k)
        k<<=1

4.混合背包

"""混合背包的问题比较简单
特点就是某些物品有无限个,有的物品只能取有限次。求解时
只需要将0-1背包和多重背包结合起来即可
p[i]:每个物品的件数,0代表无穷个
for (int i = 1; i <= n; i++)
    if (p[i] == 0)
        for (int j = w[i]; j <= V; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    else
    for (int k = 1; k <= p[i]; k++)
        for (int j = V; j >= w[i]; j--)
            f[j] = max(f[j], f[j - k*w[i]] + k*v[i]);
"""
for i in range(1,n+1):
    if p[i]==0: #完全背包
        for j in (w[i],V+1):
            f[j]= max(f[j],f[j-w[i]]+v[i])
    else :
        for k in range(1,p[i]+1):
            for j in(V,w[i]-1,-1):
                f[j] = max(f[j],f[j-k*w[i]]+k*v[i])

原文链接:https://blog.csdn.net/rwrsgg/article/details/106147165



所属网站分类: 技术文章 > 博客

作者:四季度炒肉

链接: https://www.pythonheidong.com/blog/article/377274/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

2 0
收藏该文
已收藏

评论内容:(最多支持255个字符)