01背包问题 HDU 3466

最近的一次旅行中,iSea前往了一个历史悠久的国家。经过漫长岁月的沉淀与积累,在段时间里它成为了全球最富强和最具实力的国家之一。
商家是最典型的典型商家,每个商家仅销售一件商品,其价格为Pi,但若您的资金不足以支付Qi,他们不会接受您的交易请求。
iSea将每件商品的价值评估为Vi。
问题的核心在于:如果他手头有M个货币单位,那么iSea能够获取的最大价值是多少?
输入中包含多个测试用例。

每个测试用例开始于两个整数N,M(1≤N≤500、1≤M≤5000),分别表示项目的数量及其初始金额。

接着有N行数据,每一行包含三个数值Pi,Qi和Vi(1≤Pi≤Qi≤100, 1≤Vi≤1000),这些参数的具体含义已在文中说明。

输入将以文件标记结尾终止。

一看，01背包问题
就自然套了01背包的模板，结果发现WA了

为什么呢，对于背包问题需要更深入的理解

对于这个测试样例
3 10
5 10 5
3 5 6
2 7 3

如果按照原来的背包写
结果就应该是9

为什么？

数组是这样的

    5 0 0 0 0 0 0 0 0 0
    6 6 6 6 6 6 0 0 0 0
    9 9 9 9 6 6 0 0 0 0

依次遍历每个商品时，在金额超过10的情况