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

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

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

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

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

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

数据范围
0<N,V≤1000

0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

法一：暴力dfs

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N  = 1010;

int n, m;
int v[N], w[N];

//spv表示剩余体积
int dfs(int x, int spv){
    if(x > n){
        return 0;
    }
    else if(spv < v[x]){
        return dfs(x + 1, spv);
    }
    else if(spv >= v[x]){
        return max(dfs(x + 1, spv), dfs(x + 1, spv - v[x]) + w[x]);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++){
        scanf("%d %d", &v[i], &w[i]);
    }

    int res = dfs(1, m);
    printf("%d\n", res);
    return 0;
}

法二：记忆化搜索

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N  = 1010;

int n, m;
int v[N], w[N];
int mem[N][N];  

//mem数组 表示：从第x个物品开始（x~n）， 总体积<=j 的最大价值
//spv表示剩余体积
int dfs(int x, int spv){
    if(mem[x][spv]) return mem[x][spv];  //记忆化搜索--已经找到过的就不用再找了

    int sum = 0;
    if(x > n){  //边界
        sum = 0;
    }
    else if(spv < v[x]){
        sum = dfs(x + 1, spv);
    }
    else if(spv >= v[x]){
        sum = max(dfs(x + 1, spv), dfs(x + 1, spv - v[x]) + w[x]);
    }
    mem[x][spv] = sum;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++){
        scanf("%d %d", &v[i], &w[i]);
    }

    int res = dfs(1, m);
    printf("%d\n", res);
    return 0;
}

法三：倒叙递推(从下往上推)（easy）

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N  = 1010;

int n, m;
int v[N], w[N];
//int mem[N][N];  
int f[N][N];
//f数组 表示：从第x个物品开始（x~n）， 总体积<=j 的最大价值

//spv表示剩余体积
//int dfs(int x, int spv){
//    if(mem[x][spv]) return mem[x][spv];  //记忆化搜索--已经找到过的就不用再找了

//  int sum = 0;
//    if(x > n){
//        sum = 0;
//    }
//    else if(spv < v[x]){
//        sum = dfs(x + 1, spv);  状态转移法工程
//    }
//    else if(spv >= v[x]){
//        sum = max(dfs(x + 1, spv), dfs(x + 1, spv - v[x]) + w[x]);  状态转移法方程
//    }
//    mem[x][spv] = sum;
//    return sum;
//}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++){
        scanf("%d %d", &v[i], &w[i]);
    }

    for(int i = n; i >= 1; i--){
        for(int j = 0; j <= m; j++){
            if(j < v[i]){  //背包不够装，只能不选
                f[i][j] = f[i + 1][j];  //状态转移法工程
            }
            else if(j >= v[i]){  // 背包够装 有两个选择：选 or 不选
                f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);  //状态转移法工程
            }
        }
    }
    printf("%d\n", f[1][m]);  //f[1][m]从递归搜索树上获得，也就是最后一个点（在搜索树上为头上那个顶点）(也就是递归的第一个起点)
    return 0;
}

法三：正序递推（由上至吓）（难）

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N  = 1010;

int n, m;
int v[N], w[N];
//int mem[N][N];  
int f[N][N];
//f数组 表示：从第1个物品开始（1~x）， 总体积<=j 的最大价值

//spv表示剩余体积
//int dfs(int x, int spv){
//    if(mem[x][spv]) return mem[x][spv];  //记忆化搜索--已经找到过的就不用再找了

//  int sum = 0;
//    if(x > n){
//        sum = 0;
//    }
//    else if(spv < v[x]){
//        sum = dfs(x + 1, spv);  状态转移法工程
//    }
//    else if(spv >= v[x]){
//        sum = max(dfs(x + 1, spv), dfs(x + 1, spv - v[x]) + w[x]);  状态转移法方程
//    }
//    mem[x][spv] = sum;
//    return sum;
//}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++){
        scanf("%d %d", &v[i], &w[i]);
    }

    f[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(j < v[i]){
                f[i][j] = f[i - 1][j];  //状态转移法工程
            }
            else if(j >= v[i]){
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  //状态转移法工程
            }
        }
    }
    printf("%d\n", f[n][m]);  //f[1][m]从递归搜索树上获得，也就是最后一个点（在搜索树上为头上那个顶点）(也就是递归的第一个起点)
    return 0;
}

法四：空间压缩

#include<iostream>

#include<algorithm>
#include<cstring>

using namespace std;

const int N  = 1010;

int n, m;
int v[N], w[N];
int f[N];
int g[N];

//因为f数组由两种状态决定（选还是不选）--所以就可由二维降到一维 再用g数组存下
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; i++){
        scanf("%d %d", &v[i], &w[i]);
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
           g[j] = f[j];
           if(j >= v[i]){
               g[j] = max(f[j], f[j - v[i]] + w[i]);
           }
        }
        memcpy(f, g, sizeof f);  //额。。。。。。。。。。。。。
    }
    printf("%d\n", f[m]);  //f[1][m]从递归搜索树上获得，也就是最后一个点（在搜索树上为头上那个顶点）(也就是递归的第一个起点)
    return 0;
}

法五：dfs多参数

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n, m;
int v【N】, w【N】;
int res = 0;

void dfs(int x, int sumV, int sumW) {
    if(x > n) {
        if(sumV <= m && sumW >= res) {
            res = sumW;
        }
        return ;
    }

    //不选
    dfs(x + 1, sumV, sumW);

    //选
    if(sumV + v【x】 <= m)
        dfs(x + 1, sumV + v【x】, sumW + w【x】);
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d %d", &v【i】, &w【i】);
    }

    dfs(1, 0, 0);
    printf("%d\n", res);
    return 0;
}

法六：终极优化（滚动数组）f[N] 只有一个数组

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n, m;
int v【N】, w【N】;
int f【N】;

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d %d", &v【i】, &w【i】);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= v【i】; j --) {
            if(j >= v【i】) {
                f【j】 = max(f【j】, f[j - v【i】] + w【i】);
            }
        }
    }
    printf("%d\n", f【m】);
    return 0;
}