回顾一下Codeforces1207A,https://blog.csdn.net/tomjobs/article/details/100045335
是一道800分的大水题，但还是通过此题加深了对01背包的理解
题意： 有原材料，汉堡鸡翅所需原材料不同，价格不同，问最多能卖多少钱。
思路： 我两个for枚举了所有情况。其实只需要考虑2种情况：优先换汉堡和优先换鸡翅。
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 1e6 + 7;int main()
{int T;scanf("%d",&T);while(T--){int b,p,f;scanf("%d%d%d",&b,&p,&f);int h,c;scanf("%d%d",&h,&c);int ans = 0;for(int i = 0;i <= 100;i++)//hum 2b 1p{for(int j = 0;j <= 100;j++)//chick 2b 1f{if(i * 2 + j * 2 <= b && i <= p && j <= f){ans = max(h * i + j * c,ans);}}}printf("%d\n",ans);}}
上面是原题，暴力算法的正确性无需置疑。但是，另外一个方法：只需要考虑两种情况，还是有点想头的。
1.首先简化问题，这是一个一元费用问题，这个问题其实只与a有关！
为什么呢？不是还有b和c吗，不应该是三元费用问题吗？但是思考题目模型，b和c互不影响，其实不影响题意，假设两个物品都有b，c属性，就可以算3元费用问题了，就可以引申到多元背包了。
2. 那么，为什么只需要考虑两种情况呢？在简化的模型下，每2个a可以换得一个汉堡或者鸡翅，换句话说，每两个a对应有一个贡献值。很明显，a要贪心的换成最大价格的东西。在原题中b，c的限制，本质上是限制数目，所以本质是一种选择方法——换最大价格的东西，到限制了再换另外一个东西。
3. 推广问题，假设3个a换一个汉堡，2个a换一个鸡翅，是否还有这种贪心的选择方法？
很遗憾，答案是NO。这种情况下不能只是贪心的先全部换汉堡剩下的换鸡翅，或者全部换鸡翅剩下的换汉堡。因为a的剩余！假设一个a可以换 1/3个汉堡，也可以换1/2个汉堡，那么贪心算法肯定是成立的。但是只能3个a换和2个a换，就有可能换不完,a剩下了。这种情况下你不能证明贪心算法的正确性，因为a的贡献不仅仅是价值除以数量，还与换的数目有关，因为可能换不完。
举例子说明：这是一个随机数程序，ans是暴力求出的答案，ans2是贪心2种情况求出的答案。结果是两个结果并不一定相等。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <map>
#include <cstdlib>
using namespace std;const int num1 = 2;
const int num2 = 3;
int main()
{srand(time(NULL));while(1){int x = rand() % 10000,y =rand() % 10000;int a = rand() % 10000;int ans = 0;int num_x = 0,num_y = 0;for(int i = 0;i <= 10000;i++){for(int j = 0;j <= 10000;j++){if(i * num1 + j * num2 <= a){if(ans <= i * x + j * y){ans = max(i * x + j * y,ans);num_x = i,num_y = j;}}}}int ans2 = 0;int tmp1 = a / num1 * x;int tmp2 = a / num2 * y + (a % num2) / num1 * x;ans2 = max(tmp1,tmp2);if(ans != ans2){cout << ans << ' ' << ans2 << endl;cout << x << ' ' << y << ' ' << num_x << ' ' << num_y << endl;cout << a << endl;continue;}}
}
//6201 6200
//155 388 35 2
//895//6227976 6226116
//5564 7424 1118 1
//2239- 原因很明显，是交换过程中换不完导致了a的剩余。再看看背包问题：为什么01背包贪心算法是错误的，而部分背包（可以拆开物品）贪心算法是正确的？理由和这里原因，01背包用重量换价值的过程中，可能换不整，会有剩余，剩余的部分价值不明了。而部分背包中，肯定能换完，那么可以证明，取单位重量价值贡献最大的东西，结果最优。