1.背包问题
问题描述：

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

这算是我第一次接触背包问题，按我以往的思路，要不是先写回溯的过程，要不直接写动态规划，这次这个和之前的不太一样，因为它的有两部分决定的动态规划方程，只想一个会发现找不到递推关系。eg：我们规定dp[i]为第i个物品加入的最大值，那体积不同是否是就不一定了，所以我们要用二维数组解决问题。
思路： dp[i][j]表示前i个物品在容积为j时的最大值。
这样一来，转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]); (j > v[i]时)
dp[i][j = dp[i-1][j];(j < v[i]时)
意思就是：如果当前这个物品比当前的容量还大那这件物品就不可能装进来了，那么价值就等于容量在j时前i-1个物品的价值；如果当前物品可以装进来，那么我们需要决策：即装入还是不装入当前物品？若装入，则需要预留出这个物品所需要的容量，那么价值最大值为：当前容量减去当前物品的体积的条件下的价值+当前物品的价值；若不装入，则同第一种情况，等于当前容积下前i-1个物品的价值。
最开始用的回溯：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dfs(vector<int> v, vector<int> w, int cap, int value, int index) {
    if(cap < 0) {
        //cout << "第" << index-1 << "物品放不下了,最大值为" << value-w[index-1] << endl;
        return value - w[index-1];
    }
    if(index == v.size()) {
        //cout << "遍历完成，本次尝试最大值为" << value << endl;
        return value;
    }
    
    int res = 0;
    for(int i = index; i < v.size(); i++) {
        //cout << "将第" << i << "物品加入背包中" << endl;
        res = max(res, dfs(v, w, cap-v[i], value+w[i], i+1));
        //cout << "将第" << i << "物品取出，尝试下一个物品" << endl;
    }
    return res;
}

int main() {
    int n, cap;
    vector<int> v, w;
    cin >> n >> cap;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(a);
        w.push_back(b);
    }
    cout << dfs(v, w, cap, 0, 0) << endl;
    return 0;
}

接下来看了题解，发现是这样的思路解决的

#include <iostream>
#include <algorithm>

using namespace std;

const int c = 1001;

int dp[c][c];
int v[c], w[c];
    
int main() {
    int n, cap;
    cin >> n >> cap;
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= cap; j++) {
            if(j < v[i]) dp[i][j] = dp[i-1][j];
            else {
                dp[i][j] = max(dp[i-1][j], w[i]+dp[i-1][j-v[i]]);
            }
        }
    }
    cout << dp[n][cap] << endl;
    return 0;
}

还可以优化一下空间，用一维数组代替：可以发现我们每次用的就是上一步推出来的结果，我们可以一直用一维数组覆盖掉上一步的结果即可。唯一注意的是：我们要从后向前遍历，因为递推过程中我们需要前面的结果，如果我们还是从前向后遍历那么上一步的结果就被我们覆盖掉了。

#include <iostream>
#include <algorithm>

using namespace std;

const int c = 1001;

int dp[c];
int v[c], w[c];
    
int main() {
    int n, cap;
    cin >> n >> cap;
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = cap; j >= 0; j--) {
            if(j >= v[i]) dp[j] = max(dp[j], w[i]+dp[j-v[i]]);
        }
    }
    
    cout << dp[cap] << endl;
    return 0;
}