【DP】完全背包问题

问题描述

现有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

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

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;
}