题解 | #【模板】01背包#

经典01背包问题。
解题思路比较常规。用辅助数组res存储容积为i时能装入物品的最大价值。对物品进行遍历，每次遍历中都逆序更新res，转移方程为res[j]=max(res[j-v[i]]+p[i],res[j])。最终res[v]即为要求的容积为v时所能装入物品的最大价值。
这道题设置了两问，解题上有细微差别。需要分开用两个辅助数组来存储结果。第一问求能装入物品的最大价值，没有要求刚好装满，所以直接把数组res的元素全部初始化为0即可。而第二问要求刚好装满时的最大价值。需要将res第一个元素初始化为0，代表容积为0的背包装满时最大价值为0；将其余元素全部初始化为一个很大的负数，要保证就算将所有物品的价值与这个数相加还会得到一个负数。这样，在按照与第一问同样的方法计算最大价值时，若不存在刚好装满的情况，res[v]就会为负数，因为没有办法从res[0]一直装物品装到res[v]。只有能从res[0]开始装，由于res[0]=0，才能规避掉初值的极大负值，得到一个正常的正值。所以最后判断res[0]即可，为正直接返回，为负返回0。

这里记录一下写的时候遇到的坑。
开始时将res数组初始化为大小为v的数组，提交时总有一些用例出问题。实际上这里辅助数组res[i]表示的是容积为i时能装入物品的最大价值，其范围应该是0,1,2,...,v，所以res初始化的大小应该是v+1，否则必定出错。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, v;
    cin >> n >> v;
    vector<int> arrv(n, 0);
    vector<int> arrp(n, 0);
    vector<int> res(v + 1, 0);
    vector<int> cres(v + 1, -99999);
    cres.at(0) = 0;
    for(int i = 0;i < n;i++){
        cin >> arrv.at(i) >> arrp.at(i);
    }
    for(int i = 0;i < n;i++){
        for(int j = v;j >= arrv.at(i);j--){
            res.at(j) = max(res.at(j - arrv.at(i)) + arrp.at(i), res.at(j));
            cres.at(j) = max(cres.at(j - arrv.at(i)) + arrp.at(i), cres.at(j));
        }
    }
    int max = res.at(v); 
    int comax = cres.at(v) > 0 ? cres.at(v) : 0;
    cout << max << endl << comax;
    return 0;
}

附一段递归代码，在第12个用例处超时，望大佬指点一下优化方法。

#include <iostream>
#include <vector>

using namespace std;

int n, V;
vector<int> price;
vector<int> volume;

int main(){
    cin >> n >> V;
    for(int i = 0;i < n;i++){
        int vt, vp;
        cin >> vt;
        cin >> vp;
        volume.push_back(vt);
        price.push_back(vp);
    }
    int put(int i, int v);
    int cput(int i, int v);
    cout << put(n - 1, V) << endl << (cput(0, V) > 0 ? cput(0, V) : 0);
}
int put(int i, int v){
    if(i < 0 || v == 0){
        return 0;
    }
    if(volume.at(i) > v){
        return put(i - 1, v);
    }
    else{
        return max(put(i - 1, v), put(i - 1, v - volume.at(i)) + price.at(i));
    }
}
int cput(int i, int v){
    if(i == n && v != 0){
        return -9999;
    }
    else if(v == 0){
        return 0;
    }
    else if(volume.at(i) > v){
        return cput(i + 1, v);
    }
    else{
        return max(cput(i + 1, v), cput(i + 1, v - volume.at(i)) + price.at(i));
    }
}