九大背包问题专题--二维费用的背包问题_为什么背包问题二维要全部枚举

5.二维费用的背包问题

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

每件物品只能用一次，体积是vi，重量是mi，价值是wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包的容量，总重量不可超过背包可承受的最大重量，且价值总和最大。
输出最大价值

输入格式
第一行有两个整数，N，V，M用空格隔开，分别表示物品种数、背包容积和背包能承受的最大重量。

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

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

数据范围
0<N<=1000
0<V,M<=100
0<vi,mi<=100
0<wi<=1000

输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例
8

分析思路
时间复杂度：10^7

每个物品只能用一次->01背包问题

枚举：体积，重量->从大到小枚举

f[i][j]:表示总体积是i,重量为j的情况下，最大价值是多少
状态转移：
第一层循环：枚举每个物品（从前往后）
第二层循环：枚举体积
第三层循环：枚举重量

代码：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;
int n,v,m; 
int f[N][N];

int main(){
	cin>>n>>v>>m;
	for(int i=0;i<n;i++)  //从前往后枚举物品 	
	{
	int a,b,c; 
	cin>>a>>b>>c;
	 for(int j=v;j>=a;j--) //体积从大到小枚举
	    for(int k=m;k>=b;k--) //重量从大到小枚举 
	    f[j][k]=max(f[j][k],f[j-a][k-b]+c); //转移 
	    cout<<f[v][m]<<endl;
	    return 0;
} 
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22