最近好像跟背包問題有緣啊，已經(jīng)做了好幾道了。不過感覺這個問題確有它值得研究之處，也從中學(xué)到不少東西呵＆
這道題目的大意是：有n種材料，每種材料有數(shù)量c和長度h還有一個特殊限制（可以看成一個背包的容量）
出題者要你求出用這n種材料可以累加出的最大長度而且其中的每一種材料中的任何一個元素都不能高過這個限制a.想了想，貌似可以用多重背包來形容這個問題，當(dāng)然我是非專業(yè)的，說得不恰當(dāng)還請大家原諒；
下面的這段代碼中有幾點(diǎn)值得注意：
首先是這道題中的關(guān)鍵部分和我寫的1276題非常相似（參考了網(wǎng)路上大牛的代碼 先謝過~)
通過這兩個題我發(fā)現(xiàn)：這種方法只適用于（這里我們用背包問題的原始定義來形象的說明）物品的重量等于其價值的情況；
非這種情況那就請老老實(shí)實(shí)按書上的方法做吧（如果說錯了 還望您指出，不過我是這樣認(rèn)為的）；
這種方法確實(shí)很快，而且比課本上提到的dp方法更牛，一定要掌握呵＆
其次是這道題一定要先排序，再dp;
為什么呢？我想了想 給出下面一個例子：
如果數(shù)據(jù)是這樣的：
2
7 40 3
5 23 1
如果不排序 那么按照那個算法26是不可及的
但是如果排序(按a從小到大）
變成
5 23 1
7 40 3
那么26就可能了
是不是很神奇？但這就是區(qū)別 所以本題必須要排序；
我后來又想了想 發(fā)現(xiàn)這其實(shí)是一個策略的問題，在實(shí)際中，我們也當(dāng)然會把安全的部分放在底層，這總方法感覺上就更穩(wěn)妥些，而且也帶有某種貪心的性質(zhì)我覺得。
如果哲學(xué)的來理解，我引用一句經(jīng)典的話：九層之臺，起于累土，千里之行，始于足下。呵呵，我感覺還挺符合本題的，不知道您覺得呢？
AC CODE:
#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
int h;
int a;
int c;
}a[401];
int cmp(node a,node b)
{
return a.a<b.a;
}
bool dp[40001];
int main ()
{
int n;
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].c);
}
sort(a+1,a+1+n,cmp);
int max=0;
dp[0]=true;
for(i=1;i<=n;i++)
{
for(k=max;k>=0;k--)
if(dp[k]==true)
{
for(j=1;j<=a[i].c;j++)
{
int temp;
temp=k+j*a[i].h;
if(temp>a[i].a)
break;
dp[temp]=true;
if(temp>max)
max=temp;
}
}
}
printf("%d\n",max);
return 0;
}