HDU 3449 Consumer【DP之背包】

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=3449

题意：自己看吧~~~

思路一：先对箱子里的物品进行一次01背包，然后加上箱子价格，在进行分组背包，然后TLE ！！白写了一个下午呀！！！

超时代码：

#include<stdio.h>#include<stdlib.h>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int Max = 1000000 +10;int dp[Max],N,V;int d[Max];void Zero_One(int cost , int value , int vb){    int i;    for(i = V;i >= vb+cost;i --)    {        dp[i] = max(dp[i] , dp[i-cost]+value);    }}int main(){    int i,j;    while(~scanf("%d%d",&N,&V))    {        int vb,k;        memset(d,0,sizeof(d));        for(i = 0;i < N;i ++)        {            scanf("%d%d",&vb,&k);            for(j = 0;j <= V-vb;j ++)                dp[j+vb] = d[j];            for(j = 0;j < k;j ++)            {                int cost,value;                scanf("%d%d",&cost,&value);                Zero_One(cost,value,vb);            }            for(j = vb;j <= V;j ++)                d[j] = max(d[j],dp[j]);        }        printf("%d\n",d[V]);    }}