常规类型问题描述

有多种物品，和一个最大承重量为w的背包，每种物品有weight和value，问将这些物品放入背包中（每种物品可以放多个），背包的最大价值是多少。

与0-1背包不同的是，0-1背包每件物品只能放一次，而完全背包每种物品可以无限多地放。

解决方法

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

优化后：dp[j] = max{dp[j] , dp[j - weight[i]] + value[i]}

注意与0-1背包不同的是方程右边是dp[i , j - weight[i]] + value[i]。

上代码：

#include<iostream>
using namespace std;
int n,W;
int w[1000],v[1000];
int dp[10000];
int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }

    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]);
        }
        for(int j = 0 ; j<=W ; ++j){
            cout<<dp[j]<<' ';
        }
        cout<<endl;
    }
    cout<<dp[W]<<endl;
    return 0;
}

完全背包的内层循环是正序的，而0-1背包是逆序的，为什么呢？

我们先来理解一下完全背包的状态转移方程：dp[i , j] = max{dp[i-1 , j] , dp[i , j - weight[i]] + value[i]}，在放i物品时，我们还是要考虑放还是不放？在什么基础上放？

如果是0-1背包，那么在放i物品时，由于一个物品只能放一次，所以它的基础是前面i-1个物品所更新好的背包，即j背包前面的背包的状态必须是i-1；

而如果是完全背包，在背包j里放物品i时，它的基础却是状态i的背包，即比j容量小的背包是已经被i更新过的，为什么呢？

比如容量10的背包，放weight=3的物品，那么我们只需要考虑在容量为7的背包里放weight=3的物品就好了，但不是前面说是一种物品可以放多个么，容量10的背包可以放3个weight=3的物品吧，为什么只放了一个呢？但是，由于内层循环是正序的，所以背包7的基础是4，背包4的基础是1，我们在背包4里放了一个3，在背包7里又放了一个，而背包7的基础是4，所以相当于放了2个3，所以到背包10时，想当于放了3个3，这就是为什么完全背包要正序的原因。

例题：hdu 2159 FATE

http://acm.hdu.edu.cn/showproblem.php?pid=2159

我们把耐久度当成weight，经验值当成value，求满足经验值大于n，次数小于s的最小耐久度

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;


int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n , m , k , s;
    while(cin>>n>>m>>k>>s){
        int weight[110] , value[110] , dp[110] , num[110];
        memset(weight , 0 , sizeof(weight));
        memset(value , 0 , sizeof(value));
        memset(dp , 0 , sizeof(dp));
        memset(num , 0 , sizeof(num));
        for(int i = 0 ; i<k ; ++i){
            cin>>value[i]>>weight[i];
        }
        for(int i = 0 ; i<k ; ++i){
            for(int j = weight[i] ; j<=m ; ++j){
                if(dp[j] < dp[j - weight[i]] + value[i]){
                    dp[j] = dp[j - weight[i]] + value[i];
                    num[j] = num[j - weight[i]] + 1;
                }
            }
        }
        int flag = 0;
        for(int i = 0 ; i<=m ; ++i){
            if(num[i] <= s && dp[i] >= n){
                cout<<m - i<<endl;
                flag = 1;
                break;
            }
        }
        if(!flag){
            cout<<-1<<endl;
        }
    }
}

其实还可以用二维完全背包做，把耐久度和次数都当做weight，经验当做value，每个怪物的次数这个weight都是1，题目要求输出的是最小耐久度，所以我们最终输出最大的次数，最小的>n的经验值的情况下的最小耐久度，其中最大次数保证了最小耐久度下能获得的最大经验值。

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;


int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n , m , k , s;
    while(cin>>n>>m>>k>>s){
        int weight[110] , value[110] , dp[110][110] , num[110];
        memset(weight , 0 , sizeof(weight));
        memset(value , 0 , sizeof(value));
        fill(dp[0] , dp[0] + 110 * 110 , 0);
        memset(num , 0 , sizeof(num));
        for(int i = 0 ; i<k ; ++i){
            cin>>value[i]>>weight[i];
        }
        for(int i = 0 ; i<k ; ++i){              //一种物品一种物品地放
            for(int j = weight[i] ; j<=m ; ++j){   //考虑耐久度
                for(int h = 1 ; h<=s ; ++h){      //考虑次数
                    dp[j][h] = max(dp[j][h] , dp[j - weight[i]][h-1] + value[i]);
                }
            }
        }
        if(dp[m][s] >= n){
            for(int i = 1 ; i<=m ; ++i){
                if(dp[i][s] >= n){
                    cout<<m-i<<endl;
                    break;
                }
            }
        }
        else cout<<-1<<endl;
    }
}

求装特定重量的装法总数

给一个特定的容量，必须装满
与装的顺序无关
每个物品可以装无限多次

dp[0] = 1 ;必须初始化,其他为0
for(int i = 0 ; i < n ; ++i){
    for(int j = weight[i] ; j <= w ; ++j){
        dp[j] = dp[j] + dp[j - weight[i]];
    } 
}

其中$dp[i][j]$表示考虑前$i$件物品而且装满容量$j$的背包的装法总数。

所以状态转移函数为

$dp[i][j] = sum(dp[i-1][j] , dp[i][j - weight[i]])$

也就是说，装法总数 = 我不装这个物品时的装法总数 + 装这个物品时的装法总数。

变种：背包需要装满

常规的完全背包是只要背包能装得下就往里面装，现在是背包必须装满，我们设$dp(i,j)$表示前$i$个物品来装满容量为$j$的背包的最大价值，那么我们的递推公式：

$dp(i,j) = max(dp(i-1,j) , dp(i-1 , j - weight[i]) + value[i]$

就必须保证$j - weight[i]$的背包是满的。

int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n , m;
    cin>>n;
    vector<int> weight , value;
    for(int i = 0 ; i<n ; ++i){
        int a;
        cin>>a;
        weight.push_back(a);
    }
    m = n;
    for(int i = 0 ; i<m ; ++i){
        int a;
        cin>>a;
        value.push_back(a);
    }
    int target;
    cin>>target;
    vector<int> dp(target+1 , -1);
    dp[0] = 0;  //容量为0的背包是满的
    for(int i = 0 ; i < m ; ++i){
        for(int j = weight[i] ; j <= target ; ++j){
            if(dp[j - weight[i]] != -1){//如果j - weight[i]的背包是满的
                if(dp[j] == -1 || dp[j] < dp[j - weight[i]] + value[i]){
                    dp[j] = dp[j - weight[i]] + value[i];
                }
            }
        }
        for(auto h : dp){
            cout<<h<<' ';
        }
        cout<<endl;
    }
    cout<<dp.back();
}