题目内容

有 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

题解

背包问题的状态表示：
令，f[i][j] 表示只看前i个物品，总体积是j的情况下的最大价值。
那么，result = max{f[n][0~V]}

f[i][j]存在以下两种情况:
case1 不选第i件物品，f[i][j] = f[i - 1][j]
case2 选第i件物品，f[i][j] = f[i - 1][j - V[i]] + w[i]
f[i][j] = max{case1, case2}

设置f[0][0] = 0

代码

////采用二维数组的算法代码
// #include <iostream>
// #include <cstring>
// #include <algorithm>

// using namespace std;

// const int N = 1010;

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

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

//采用一维数组的算法代码
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int f[N];//表示体积为i的情况下的最大价值
int v[N],w[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j>= v[i]; j--) 
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    
    /*
    f[0] = 0;
    当f[i] = 0时，f[m] 体积代表小于等于m的情况下的最大价值
    当f[i] = -INF时，f[m]体积代表等于m的情况下的最大价值
    */
    cout << f[m] << endl; 
    
    return 0;
}