E4 01背包 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1048 ↗

题目描述

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$ ，价值是 $D_i$ 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

第一行：物品个数 $N$ 和背包大小 $M$ 。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$ 。

输出格式

输出一行最大价值。

输入输出样例 #1

输入 #1

plaintext

输出 #1

plaintext

算法解析：#

01 背包： $f[j]$ 表示容量 $j$ 能装下的最大价值。对每个物品，容量从大到小遍历（ $j$ 逆序）， $f[j]=\max(f[j], f[j-w]+v)$ ，逆序保证每个物品最多取一次（避免重复使用）。复杂度 $O(nm)$ ，空间可压缩为一维。

Python代码实现#

N = 3410
M = 13000
n, m = map(int, input().split())
v = [0] * N
w = [0] * N
f = [0] * M
for i in range(n):
    v[i + 1], w[i + 1] = map(int, input().split())
for i in range(1, n + 1):
    for j in range(m, 0, -1):
        if j >= v[i]:
            f[j] = max(f[j], f[j - v[i]] + w[i])
        else:
            break
print(f[m])

python

C++代码实现#

// 逆序枚举，优化空间#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=3410,M=13000;
int n, m;
int v[N],w[N],f[M];

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--)  //枚举体积
      f[j]=max(f[j],f[j-v[i]]+w[i]);

  printf("%d\n",f[m]);
}