【动态规划】01背包问题

分手后的思念是犯贱 2023-07-06 06:12 169阅读 0赞

**01背包问题**

有n件物品，每件物品的重量为w\[i\]，价值为c\[i\]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有一件。

令 dp\[i\]\[j\] 表示前 i 件物品装入容量为 j 的背包所能得到的最大总价值。

对于 dp\[i\]\[j\] 来说，i 指的是前 i 件物品，j 指的是还剩下多少背包空间。于是对于dp\[i\]\[j\]来说，有公式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]

**经典01背包裸题**

[例题：hdu 2602 Bone Collector][hdu 2602 Bone Collector]

**一般做法：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    struct node{ 
        int val,vol;
    }a[1010];
    int dp[1010][1010];
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            memset(dp,0,sizeof(dp));
            int n,v;    cin>>n>>v;
            for(int i=1;i<=n;i++)
                cin>>a[i].val;
            for(int i=1;i<=n;i++)
                cin>>a[i].vol;
            for(int i=1;i<=n;i++){ 
                for(int j=0;j<=v;j++){ 
                    if(a[i].vol>j)  dp[i][j]=dp[i-1][j];
                    else dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].vol]+a[i].val);
                }
            }
            cout<<dp[n][v]<<endl;
        }
    }

**滚动数组优化：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    struct node{ 
        int val,vol;
    }a[1010];
    int dp[1010];      //表示该容量背包的最大价值
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            memset(dp,0,sizeof(dp));
            int n,v;    cin>>n>>v;
            for(int i=1;i<=n;i++)
                cin>>a[i].val;
            for(int i=1;i<=n;i++)
                cin>>a[i].vol;
            for(int i=1;i<=n;i++){ 
                for(int j=v;j>=a[i].vol;j--)    //反过来循环，避免被覆盖
                    dp[j]=max(dp[j],dp[j-a[i].vol]+a[i].val);
            }
            cout<<dp[v]<<endl;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216160649470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70
[hdu 2602 Bone Collector]: http://acm.hdu.edu.cn/showproblem.php?pid=2602