0%

二维费用的背包问题


完全背包问题的模型如下:
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 $v_i$,重量是 $m_i$,价值是 $w_i$。求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值。

输入格式
第一行两个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 $v_i,m_i,w_i$,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数,表示最大价值。
数据范围

  1. $0<N≤1000$
  2. $0<V,M≤100$
  3. $0<v_i,m_i≤100$
  4. $0<w_i≤1000$
1
2
3
4
5
6
7
8
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例:
8

思路:多了一维重量限制,其实和01背包是一样的多枚举一下重量即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m,w;
int f[N][N];
int main(){
cin>>n>>m>>w;
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
for(int j=m;j>=a;j--){
for(int k=w;k>=b;k--){
f[j][k] = max(f[j][k],f[j-a][k-b]+c);
}
}
}
cout<<f[m][w]<<endl;
return 0;
}