0-1背包&完全背包

桃扇骨 2022-05-28 12:24 193阅读 0赞

# **First：0-1背包问题** #

1.定义define：

所谓的0-1背包就是指每种物品只有一件，而每件物品只有两种选择，即选择放或是不放

2.问题：

一个小偷来出来活动了， 拿了一个背包， 最多可以装50斤的东西的小袋子。 他眼睛一亮， 发现了三件宝贝a, b, c. 其中a重10斤， 价值60元; b重20斤， 价值100元; c重30斤， 价值120元。 问： 在背包允许的范围内， 小偷最多能偷到多少钱？简单的说就是现有N种物品和重量为V的背包，第i件物品的重量为c\[i\]，价值为w\[i\]，求解将哪些物品放入背包可使价值总和达到最大。

3.思路：

在背包所能承受的最大容量下得到最大价值

子问题状态:f\[ j \]的含义：表示前i件物品放入容量为j的背包的情况下价值的最优解

状态转移方程：f\[j\] = max\{f\[j\],f\[j - weight\[i\]\] + value\[i\]\}

初始化：（因为f 数组中存的是前i件物品放入j容量的背包的最大价值）f数组初始值定义为0

4.code精华：

for(i=0;i<N;i++)
    {
        for(j=V;j>=weight[i];j--)
            f[j]=max(f[j],f[j-weight[i]]+value[i]);
    
    }

我们可以顺着这个for循环一起走两趟，设N=3，V=5，weight\[N\]=｛1，2，3｝，value\[N\]=｛6，10，10｝，一开始背包里没有装任何物品，所以一开始初始值f\[0\]=f\[1\]=f\[2\]=f\[3\]=f\[4\]=f\[5\]=0;接下来我们一起走循环，![70][]![70 1][]![70 2][]

5.完整代码：

#include <bits/stdc++.h>
        using namespace std;
        int n,v,weight[5],value[5],f[10];
        int ZeroOnePack()
        {
            memset(f,0,sizeof(f));
            for(int i=0;i<n;i++)
            {
                for(int j=v;j>=weight[i];j--)
                {
                    f[j]=max(f[j],f[j-weight[i]]+value[i]);
                    cout<<j<<" "<<f[j]<<endl;
                }
            }
            return f[v];
        }
        int main()
        {
            int t;
            cin>>n>>v;
            for(int i=0;i<n;i++)
                cin>>weight[i];
            for(int i=0;i<n;i++)
                cin>>value[i];
            t=ZeroOnePack();
            cout<<t<<endl;
    
            return 0;
    
       }

# **Second：完全背包问题** #

1.定义：

完全背包和0-1背包最大的区别就是完全背包中每种物品有无限个，即在不超过背包容量下，可以拿多个价值一样大的物品。

2.code精华：

int CompletePack()
    {
        memset(f,0,sizeof(f));
        for(i=0;i<n;i++)
        {
                for(j=weight[i];j<=v;j++)
                {
                    f[j]=max(f[j],f[j-weight[i]]+value[i]);
                    cout<<j<<" "<<f[j]<<endl;
                }
        }
        return f[v];
    
    }

其他的和0-1背包是类似的，可以对比着看看

3.例题：[http://poj.org/problem?id=1384][http_poj.org_problem_id_1384]（Piggy-Bank）

题意：现有一个小猪存钱罐，里面存有不同种类的硬币，求在不打碎小猪的情况下，算出存钱罐中最少有多少钱。给出空小猪的重量、小猪和硬币的总重量、每种硬币单个的价值和重量，输出给定总重量的硬币可以实现的最小金额，如果无法准确达到重量，就输出“这是不可能的”。

Sample Input：

3  
10 110  
2  
1 1  
30 50  
10 110  
2  
1 1  
50 30  
1 6  
2  
10 3  
20 4

Sample Output：

The minimum amount of money in the piggy-bank is 60.  
The minimum amount of money in the piggy-bank is 100.  
This is impossible.

思路：这里求的是最小值，但其实万变不离其中，它的动态转移方程为：dp\[j\]=min(dp\[j\],dp\[j-w\[i\]\]+v\[i\]);

My Code：

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<string>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int INF = 1e9;
    int main()
    {
        int t,n,E,F,v[505],w[505],f[10005];
        cin >> t;
        while(t--)
        {
            cin >> E >> F;
            int W = F-E;
            for(int i = 0; i <= W; i++) f[i] = INF;///要求最小值，初始化为无穷大
            cin >> n;
            f[0] = 0;
            for(int i = 0; i < n; i++)
            {
                cin >> v[i] >> w[i];
                for(int j = w[i]; j <= W; j++)
                    f[j] = min(f[j],f[j-w[i]]+v[i]);
            }
            if(f[W] == INF)///如果硬币总重量的价值还是初始值的话，则说明无法达到准确重量
                printf("This is impossible.\n");
            else
                printf("The minimum amount of money in the piggy-bank is %d.\n",f[W]);
        }
    }

# **总结：（0-1背包与完全背包的比较）** #

假设求容量 j 的最大价值 f \[ j \]，f\[ j \] = max( f \[ j \], f \[ j-weight\[i\] \] + value\[i\] )，由于完全背包中物件有无限个，那么 f \[ j-weight\[i\] \]中可能已经取过物件 i 了，因此for循环是正着走的，因为它可以一直取同一个物件，最终求出满足容量的最大价值；而0-1背包每个物件只有一个，它的f \[ j-weight\[i\] \]中一定没取物件 i ，因此for循环是倒着走的，以防多取了同一个物件。

[70]: https://img-blog.csdn.net/20180405191812816?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180405192247221?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220528/c19e20c642294fcbb30b1a28f677f5ef.png
[http_poj.org_problem_id_1384]: http://poj.org/problem?id=1384