题目链接
洛谷 P2639 [USACO09OCT] Bessie's Weight Problem G
0-1 背包
注意到这里每一件物品的体积即为 \(s_i\)，但未给出价值。仔细读题，询问的是最多可以吃到的干草质量，那么价值就是每捆干草的质量，也为 \(s_i\)，是一类特殊的背包。
#include<bits/stdc++.h>
using namespace std;const int N=505,H=45010;
int h,n;
int s[N],dp[H];int main(){scanf("%d%d",&h,&n);for (int i=1;i<=n;++i) scanf("%d",s+i);for (int i=1;i<=n;++i){for (int j=h;j>=s[i];--j) dp[j]=max(dp[j],dp[j-s[i]]+s[i]);}printf("%d",dp[h]);return 0;
}
可行性背包
也可以考虑开一个布尔数组 \(dp\)，\(dp_i\) 表示能否使选出的干草质量为 \(i\)，统计时倒序遍历输出第一个（即最大的）满足的下标。此处不再赘述。