洛谷 P2639 [USACO09OCT]Bessie的体重问题

一开始以为是贪心 后来通过样例数据看不是的（良心的样例） 所以就用了DP

其实我还是不明白为什么不是贪心 有大神能解答一下吗~~~

这个动态转移方程很接近于01背包 包括我看到的很多题解 也都说这就是01背包 但我以为 这两者仅仅是类似而非一样

我以为 做动规题目 不能简单简单地想着套几个模型 而是要不断地从每一个状态来分析 （当然啦 我的愚见）

//P2639 [USACO09OCT]Bessie的体重问题 //2016.11.18 #include <cstdio> #include <iostream> using namespace std; int h, n; int f[45000], w[500 + 1]; int main(){ scanf("%d%d", &h, &n); for (int i = 1; i <= n; i++) scanf("%d", &w[i]); for (int i = 1; i <= n; i++) for (int j = h; j >= w[i]; j--) //特别注意 j要大于等于w[i] 因为一会儿要相减!!! f[j] = max(f[j], f[j - w[i]] + w[i]); printf("%d", f[h]); return 0; }