b135 - NOIP2006 2.金明的预算方案

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=b135
題解：01背包問題、有限制條件、DP

內容：
跟一班01背包問題的不同點，在於有一些物品分成主要的跟附加的。若要拿取附加的物品，則其主要物品必須拿取。主要物品不會是主要物品另一附加物品。

解題方法：
令DP[n][W][p]，其中n必須為主商品的編號，代表考慮完n號主商品及其附加商品，花費洽W下，價值和的最大值。其中p=0代表不拿主商品，p=1則為拿主商品。

轉移方法先考慮主商品的部分，p=0很簡單就不多提，那p=1時，若當前狀態W不足以支付主商品，則令值等於0。然後再考慮該主商品之附加商品，轉移時小心當前狀態及轉移狀態DP[n][W][1]都不能為0，才能滿足題目要求的「若要拿取附加的物品，則其主要物品必須拿取」。

此外該作法有跳編號的狀況(雖然可以避免XD)，故用額外的變數pn,pl,代表當前與前一個主商品的編號。

小技巧：由於題目保證價錢都是10的倍數，可以先除掉，輸出時再乘回來就好。

[C++] 純文本查看 復制代碼

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;

struct item{
        int v;
        int p;
        int w;
};

item obj[61];
vector<item> part[61];

int dp[61][3200][2];

int main()
{
        int V,N,pn,pl;
        while(~scanf("%d%d",&V,&N))
        {
                V/=10;
                for(int i=1;i<=N;++i)
                        part[i].clear();
                for(int i=1;i<=N;++i)
                {
                        scanf("%d%d%d",&obj[i].v,&obj[i].p,&obj[i].w);
                        obj[i].v/=10;
                        if(obj[i].w)
                                part[obj[i].w].push_back(obj[i]);
                }
        
                memset(dp,0,sizeof(dp));
                pn=pl=0;
                for(int i=1;i<=N;++i)
                {
                        if(obj[i].w)
                                continue;
                        pl=pn;
                        pn=i;
                        for(int j=0;j<=V;++j)
                        {
                                dp[pn][j][0]=max(dp[pl][j][0],dp[pl][j][1]);
                                if( j-obj[i].v < 0 )
                                        dp[pn][j][1]=0;
                                else
                                        dp[pn][j][1]=obj[i].v*obj[i].p+max(dp[pl][j-obj[i].v][0],dp[pl][j-obj[i].v][1]);
                        }

                        for(int k=0 ; k<part[i].size() ; ++k)
                        {
                                item &t=part[i][k];
                                for( int j=V; j>=t.v ;--j )
                                {
                                        if( dp[pn][j-t.v][1] && dp[pn][j][1] )
                                                dp[pn][j][1] = max( dp[pn][j][1] , dp[pn][j-t.v][1]+t.v*t.p ); 
                                }
                        }
                }
                int ans=0;
                for(int i=0;i<=V;++i)
                {
                        ans =max(ans ,dp[pn][i][0] ); 
                        ans =max(ans ,dp[pn][i][1] ); 
                }
                printf("%d\n",ans*10);
        }
}