| Problem Description After months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides to spend all his money on them in a sneaker store.  |
| Input Input contains multiple test cases. Each test case begins with three integers 1<=N<=100 representing the total number of products, 1 <= M<= 10000 the money Iserlohn gets, and 1<=K<=10 representing the sneaker brands. The following N lines each represents a product with three positive integers 1<=a<=k, b and c, 0<=b,c<100000, meaning the brand’s number it belongs, the labeled price, and the value of this product. Process to End Of File. |
| Output For each test case, print an integer which is the maximum total value of the sneakers that Iserlohn purchases. Print "Impossible" if Iserlohn's demands can’t be satisfied. |
| Sample Input 5 10000 31 4 62 5 73 4 991 55 772 44 66 |
| Sample Output 255 |
| 分组背包 1<=N<=100 产品数1<=M<=10000 钱1<=K<=10 品牌数1<=a<=k, b and c, 0<=b,c<100000 a是品牌数,b是价格,c是价值第i行上的各个值是加入第i个品牌后实现的最大效益。值得注意的是，这第i行的各个值都是经过第i个品牌的种类个数次得到的。以f(i, j)为例如果，第i个品牌的产品一个都还没放进去了，那么f(i, j)可以是其他第i-1个品牌的最大效益+放入这个品牌的这个种类的效益当然，这样还没完，还得与原来这个值进行比较，总之取大值如果，第i个品牌的产品已经有放进去了，那么还可以有另一种途径得到这个值那就是这i品牌，买多个种类的，看哪个大，就取哪个思路-----只需看这里就行了 因为每个品牌有多种种类，所以你用一般的方法可以得到矩阵的每一行，又考虑到每个品牌只能买一次，所以，除非是第一次，要不然你每个品牌的第一个物品都得买如果到最后，即使是每个品牌的最便宜的都买不起，那就输出impossible了编程 对于这个大矩阵，应该有10行，10000列在来几个矩阵，用来存放每个品牌中种类的价格和价值，显然得需要两个矩阵，都是10行，100列如价格矩阵a[i][j], 表示第i个品牌，第j个种类的价格 |
| Code   View Code |
| Key Points Firsly, you must clear your mind. Secondly, don't forget to initilize every time. |