E9 二维背包 • EH's Blog

题目情境#

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

题目描述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M 。

每件物品只能用一次。体积是 vi ，重量是 mi ，价值是 wi 。

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

输入格式

第一行三个整数，N,V,M ，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

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

输出格式

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

输入 #1

plaintext

输出 #1

plaintext

数据范围

0<N≤1000

0<V,M≤100

0<vi,mi≤100

0<wi≤1000

算法解析：#

二维费用背包：每个物品有两个代价（体积 $v$ 和重量 $w$ ）。状态 $f[j][k]$ 表示体积 $\le j$ 且重量 $\le k$ 的最大价值。转移 $f[j][k]=\max(f[j][k], f[j-v][k-w]+val)$ ，两个维度都逆序（01 背包）。复杂度 $O(n\cdot V\cdot W)$ 。

py代码实现#

略

C++代码实现#

//二维费用 01背包
#include <iostream>
using namespace std;

int f[110][110];
// f[j,k]:前i个物品，体积≤j，重量≤k 的最大价值

int main(){
  int n, V, W;    //物品 容量 承重
  int v, w, val;  //体积 重量 价值
  cin>>n>>V>>W;
  for(int i=1; i<=n; i++){  //物品 
    cin>>v>>w>>val;
    for(int j=V; j>=v; j--) //体积
    for(int k=W; k>=w; k--) //重量
      f[j][k]=max(f[j][k],f[j-v][k-w]+val);
  }
  cout<<f[V][W];
}