贝茜的体重问题 题解

占领无人区~
01背包变形水题 每捆干草的价值和代价都是它自己的重量 套模版就行了
记得优化一维数组

#include <bits/stdc++.h>
using namespace std;
int H,N;//不超过H干草,一共N捆干草
int a[505];//存储干草每捆的量 
int DP[45005];//当干草上限为v时所能获得的最大干草数 
int main(){
	cin>>H>>N;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	for(int i=1;i<=N;i++){
		for(int v=H;v>=a[i];v--){
			DP[v]=max(DP[v],DP[v-a[i]]+a[i]);
		}
	} 
	cout<<DP[H];
	return 0;
}