P1507 NASA的食物计划

发布时间 2023-11-11 22:55:49作者: yufan1102

image

image

还是选与不选的问题并且只能选一次,所以是01背包,但是这个题目是个二维的01背包,因为它必须要满足两个条件,这个是满足体积的情况下,一个是满足质量的情况下

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int f[N][N];
int a[N],b[N],w[N];
int main(){
	int n,m;
	cin>>n>>m;
	int x;
	cin>>x;
	for(int i=1;i<=x;i++){
		cin>>a[i]>>b[i]>>w[i];
	}
	for(int i=1;i<=x;i++){
		for(int j=n;j>=a[i];j--){
			for(int k=m;k>=b[i];k--){
				f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+w[i]);
			}
		}
	}
	cout<<f[n][m];
	return  0;
}