hdu 4501 小明系列故事——買年貨（多維背包）

剛開始比較容易想到小明又兩種包，一種是錢，一種是積分。當時讓我很糾結的是免費贈送的k件物品該怎麼使用。苦思良久，拿最貴的話，因為有兩種價格，這兩種價格可能沖突；拿實際價值最高的吧，這個物品的標價卻可能非常低，甚至是免費。這個k的使用條件讓我很糾結。

當時就在想這個k的使用條件應該是什麼樣的，是靜態的還是動態的。想到這兒突然就明白了，這個k值不就是小明的第三種背包嘛！

按說能想到這兒這道題就算做出來了，可我在寫判定條件的時候腦子不知道怎麼就抽筋了，我在比較的時候，是拿dp[j][k][l]分別和其他幾種條件比，而不是用temp去比。當時想的是如果用temp，那麼在三次比較中c[i]豈不是要加三次？

我得有多笨！

#include<stdio.h>
#include<string.h>
#define N 105
int dp[N][N][10];
int Max(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int main()
{
    int n,v1,v2,t;
    int a[N],b[N],c[N];
    int i,j,k,l;
    while(scanf("%d%d%d%d",&n,&v1,&v2,&t)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
        {
            for(j=v1;j>=0;j--)
                for(k=v2;k>=0;k--)
                    for(l=t;l>=0;l--)
                    {
                        int temp=0;
                        if(l>0)
                            temp=Max(temp,dp[j][k][l-1]+c[i]);
                        if(k>=b[i])
                            temp=Max(temp,dp[j][k-b[i]][l]+c[i]);
                        if(j>=a[i])
                            temp=Max(temp,dp[j-a[i]][k][l]+c[i]);
                        dp[j][k][l]=Max(dp[j][k][l],temp);
                    }
        }
        printf("%d\n",dp[v1][v2][t]);
    }
    return 0;
}