完全背包

发表于
字数统计: 451 | 阅读时长 ≈ 2

完全背包

代码存档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define N 505
#define MAX 100005
using namespace std;
int w[N],v[N];//w[i]为重量，v[i]为价值


int fullbagVer1(int n,int W)//动态规划实现完全背包,i为第i件商品，j为剩余容量，n为商品数量，W为重量剩余,f[i][j]为此状态下的最大价值
{
    int f[n*2][MAX];
    for(int i=1;i<=n;i++)
        f[i][0]=0;
    for(int i=1;i<=n;i++)
    for(int j=W;j>=1;j--)
    for(int k=0;k<=j/w[i];k++)
        f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*v[i]);//实际上只是转化为了01背包
    return f[n][W];
}

int fullbagVer2(int n,int W)//完全背包的子问题优化后得到的算法
{
    int f[n*2][MAX];
    for(int i=1;i<=n;i++)
        f[i][0]=0;
    for(int i=1;i<=n;i++)
    for(int j=W;j>=1;j--)
    f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
    return f[n][W];
}

int fullbagVer3(int n,int W)
{
    int f[MAX];
    f[0]=0;//memset(f,0,sizeof(f));//注意有两种初始化的方法
    for(int i=1;i<=n;i++)
    for(int j=w[i];j<=W;j++)
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    return f[W];
}

int main()
{
    int n,W;//n为数目，v为背包上限
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
        cin >> v[i];//价值
    for (int i = 1; i <= n; i++)
        cin >> w[i];//重量
    //while(1);
    cout<<fullbagVer1(n,W)<<endl;
    cout<<fullbagVer2(n,W)<<endl;
    cout<<fullbagVer3(n,W)<<endl;
    return 0;
}

注意压缩空间之后完全背包几乎和01背包一模一样，只是j的遍历方向01背包为反向，而完全背包的为正向。

参考博客：

背包九讲——CSDN

裸题：

https://hihocoder.com/problemset/problem/1043