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