P2639 [USACO09OCT] Bessie's Weight Problem G

发布时间 2023-11-11 22:50:41作者: yufan1102

image

image

大概就是在不超过容量的情况下,问你最多能吃多少

是吃与不吃,选与不选的问题,所以是01背包,但是是变式

#include<bits/stdc++.h>
using namespace std;
const int N=5e4;
int f[N],t[1000];
int main(){
	int T,n;
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=T;j>=t[i];j--){
			f[j]=max(f[j],f[j-t[i]]+t[i]);
		}
	}
	cout<<f[T];
	return 0;
}