【DP】完全背包问题

超、凢脫俗 2023-07-10 08:29 9阅读 0赞

**问题描述**

现有n个物体和容量为V的背包，每个物体i都有对应的重量w\[i\]和价值v\[i\]，每个物体可以拿无数次，在所取物体总重量不超过V的情况下，能获得的最大价值是多少？

**与 01 背包问题的区别**

*  与 01 背包问题的区别就在于物品可以拿无数次。
 *  01 背包问题是逆序遍历重量，因为如果正向遍历的话 dp\[j-w\[i\]\] 的值会因为物品重选而发生改变，无法满足每个物体只拿一次条件下的 dp\[j\] 。
 *  通过简单的推导后不难发现，当我们正序地从 w\[i\]->V 处理物体i时，dp\[j\] 正是在前 i 件物体中，在满足总重量小于 V 并且可重复拿取的情况下所得到的最大价值，刚好符合完全背包的要求。
 *  综上所述，只需要将01背包中的内层循环从逆序改为正序，就能满足完全背包，最后 dp\[V\] 就是答案。

**一般代码：**

void solve(){ 
        for(int i=1;i<=n;i++){ 
            for(int j=0;j<=W;j++){ 	//顺序遍历
                if(j<w[i])	
                	dp[i][j]=dp[i-1][j];
                else 	
                	dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
            }
        }
        printf("%d\n",dp[n][W]);
    }

**优化为一维数组：**

int dp[MAX_W+1];
    void solve(){ 
        for(int i=0;i<n;i++)
            for(int j=w[i];j<=W;j++)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        printf("%d\n",dp[w]);
    }

**例题**

[【HDU】2159 - FATE ][HDU_2159 - FATE]

**思路：** 完全背包问题，但有次数的限制。

**Code：**

#include <iostream>
    #include <cstring>
    using namespace std;
    int dp[110][110],v[110],w[110];
    int main(){ 
        int n,m,k,s;
        while(cin>>n>>m>>k>>s){ 
            memset(dp,0,sizeof(dp));
                cin>>v[i]>>w[i];
            int vis=0;
            for(int i=1;i<=m;i++){ 
                for(int j=0;j<k;j++){ 
                    for(int kk=1;kk<=s;kk++){ 
                        if(w[j]<=i)
                            dp[i][kk]=max(dp[i][kk],dp[i-w[j]][kk-1]+v[j]);
                    }
                }
                if(dp[i][s]>=n){ 
                    cout<<m-i<<endl;
                    vis=1;
                    break;
                }
            }
            if(!vis)    cout<<-1<<endl;
        }
        return 0;
    }

[HDU_2159 - FATE]: http://acm.hdu.edu.cn/showproblem.php?pid=2159