题目

描述

    北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。     注意：由于需要营养多样化，每种菜只能点一次。

输入描述：

    输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。

输出描述：

    输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。

输入：

90 4
20 25
30 20
40 50
10 18
40 2
25 30
10 8

输出：

95
38

分析

 0-1背包问题自己想听抽象的，但其实相对前面的最长递增子序列而言真的挺简单的

 （回头想录个视频来好好分析一下~别急）

解答（时间O(n*m)，空间O(n*m)）

（飘过~击败牛客网3%hhhhhhh~）

/*
-------------------------------------------------
   Author:       wry
   date:         2022/3/5 14:54
   Description:  0-1bag
-------------------------------------------------
*/

#include 

using namespace std;

const int MAXN = 1000+10;
int price[MAXN][MAXN];    //总价值
int weight[MAXN];
int value[MAXN];

int main() {
    int n,m;    //n表示物品数目、m表示背包最大容量
    while (cin >> m >> n) {
        memset(price,0, sizeof(price));
        for (int i=1;i<=n;i++) {
            cin >> weight[i] >> value[i];
        }
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if (j<weight[i]) {
                    price[i][j] = price[i-1][j];
                }
                else {
                    price[i][j] = max(price[i-1][j-weight[i]]+value[i],price[i-1][j]);    //判断到底是牺牲空间给i物品的总价值高还是保持没有i物品时背包容量是j的价值高
                }
            }
        }
        cout << price[n][m] << endl;
    }
    return 0;
}

优化代码（时间O(n*m)，空间O(m)）

 （优化十分巧妙，因为在上面的代码中，每一行的price的值都只取决于上一行的值（max(price[i-1][j-weight[i]]+value[i],price[i-1][j])）可以很清晰看见i行都是取决于i-1行，因此优化的方案就是不再使用二维数组，只用一维数组，每次更新从后往前更新，这样就不会出现覆盖错误！我只能说——妙啊~（超过80%hhhhhh~））

/*
-------------------------------------------------
   Author:       wry
   date:         2022/3/5 14:54
   Description:  0-1bag
-------------------------------------------------
*/

#include 

using namespace std;

const int MAXN = 1000+10;
int price[MAXN];    //总价值(从后向前更新)
int weight[MAXN];
int value[MAXN];

int main() {
    int n,m;    //n表示物品数目、m表示背包最大容量
    while (cin >> m >> n) {
        memset(price,0, sizeof(price));
        for (int i=1;i<=n;i++) {
            cin >> weight[i] >> value[i];
        }
        for (int i=1;i<=n;i++) {
            for (int j=m;j>=1;j--) {    //每次从后往前更新
                if (j>=weight[i]){
                    price[j] = max(price[j-weight[i]]+value[i],price[j]);    //判断到底是牺牲空间给i物品的总价值高还是保持没有i物品时背包容量是j的价值高
                }
//                else{
//                    price[j] = price[j];
//                }
            }
        }
        cout << price[m] << endl;
    }
    return 0;
}