01背包

• 01背包
  • 题目
  • 题解

01背包

题目

有 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

题解

首先由题意知，每个物品只能使用一次，找出最大价值。

没优化（二维数组）

1. f[i][j] 表示 前i个物品，背包容量j情况下，最大价值是多少。
   • 当前状态依赖于之前的状态，可以理解为，有N件物品，每次对第i件物品进行决策，基于前 i - 1件物品的最大价值下，进行判断当前物品放不放进去。
2. 当背包容量不够时（j < v[i]）, 当前位置最优解就是前 i - 1 个物品 容量为 j 的最优解。
3. 当前背包容量够，需要进行决策，选或者不选第 i 个物品， 找出最优解。
   • 因此需要进行最大值取值，分别求出选和不选的价值大小，然后进行取最大值。
   • 选：f[i][j] = f[i - 1][j - v[i]] + w[i]
   • 不选：f[i][j] = f[i - 1][j]}

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int W[N], V[N];
int n, v;
int f[N][N];

int main() {
    scanf("%d%d", &n, &v);
    // 读取数据
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &V[i], &W[i]);
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= v; j ++ ) {
            // 当前背包容量装不下第i个物品， 则价值等价于前i- 1个物品
            if (j < V[i])
                f[i][j] = f[i-1][j];
            // 能装，判断进行决策是否选择第i个物品
            else
                f[i][j] = max(f[i - 1][j], f[i - 1][j - V[i]] + W[i]);
        }
    
    printf("%d", f[n][v]);
    return 0;
}

优化后（一维数组）

1. f[j] 表示 N 件物品，在背包容量 j 下的最优解。
2. 需要注意的是：枚举背包容量时，从最大容量开始递减背包容量
3. 逆序的原因是因为，背包前面的容量代表的是到i - 1个物品时的最优解，且判断第 i 件物品，当前 j 容量下，需要使用到（前 i - 1 件物品 j 容量下）以及（减去第 i 件物品体积的最优解加上第 i 件物品的价值）的最优解。
4. 判断条件就是在容量够的情况下， 选择和没选择时最大价值的：f[j] = max(f[j], f[j - v] + w)
   • 选：f[j] = f[j]
   • 不选：f[j] = f[j - v] + w

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;

int f[N];


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

    printf("%d", f[m]);
    return 0;
}