天天看點

【分組背包問題 (HDU 3535 )】

用到至少選擇一個,是以沒有空間優化

分組背包問題:

常見的三種分組問題:

分成K組:

1、每組最多隻能取一件物品

一維數組僞碼:

for 0 to K  對每一組進行

    for W to 0   對每一個代價進行判斷 ///1

     for all item i in group k        ///2 這行個互換好像也對

     dp[w]=max(dp[w],dp[w-c[i]]+v[i];   每個重量保證的隻有一件物品來取最大值

2、每組随意取(為01背包問題)******摘抄網絡**既然上面的順序是限制每組最多取一個,那調換一下順序即可,其實就是01背包。******

一維僞碼:

for 0 t0 K

    for all item i in group k

      for W to 0

      dp[w]=max(dp[w],dp[w-c[i]]+v[i]);

3、每組至少取一個

沒見過一維的僞代碼

用二維:

dp[ki][j]表示目前組的一件物品不選

dp[ki-1][j-w[i]]+v[i] 表示這是在ki組選第一個

dp[ki][j-w[i]]+v[i] 表示在這個ki組中再次選一個

dp[ki][j](處理完後的值)=max(dp[ki][j],dp[ki-1][j-w[i]]+v[i],dp[ki][j-w[i]]+v[i]) max分開的時候要注意順序 max(dp[ki][j],dp[ki-1][j-w[i]]+v[i])......

在初始化時是ki==0(沒有組)這時是dp[0][j]=0 其餘的是-inf ******解決一件物品都不取的問題

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define X 10005
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int n,t;
    int m,s;
    cin>>n>>t;
    int dp[105][105];
    int  c[105],g[105];
    memset(dp,-inf,sizeof(dp));
    memset(dp[0],0,sizeof(dp[0]));
    for(int i=1;i<=n;++i)//k組
    {
        cin>>m>>s;
        for(int j=0;j<m;++j)
        {
            scanf("%d%d",&c[j],&g[j]);
        }
            if(s==0)
            {
            // for(int j=0;j<=t;++j)
              //  dp[i][j]=-1000000;
            for(int j=0;j<m;++j)
                for(int p=t;p>=c[j];--p)
            {
                dp[i][p]=max(dp[i][p],dp[i][p-c[j]]+g[j]);
                dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);

            }
           }
          else if(s==1)
           {
            for(int j=0;j<=t;++j)
              {
                  dp[i][j]=dp[i-1][j];//目前i個組繼承前i-1個組
              }
                for(int j=0;j<m;++j)
                {
                    for(int p=t;p>=c[j];--p)
                    {
                        dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);
                    }
                }

           }
        else if(s==2)
        {
            for(int j=0;j<=t;++j)
                {
                    dp[i][j]=dp[i-1][j];
                }
             for(int j=0;j<m;++j)
            {
                for(int p=t;p>=c[j];--p)
                {
                   // dp[i][p]=max(dp[i][p],dp[i-1][p]);//不取
                    dp[i][p]=max(dp[i][p],dp[i][p-c[j]]+g[j]);//多個
                    //dp[i][p]=max(dp[i][p],dp[i-1][p-c[j]]+g[j]);//一個

                }
            }
        }
    }
   // if(dp[n][t]<0)
  //      cout<<-1<<endl;
  //  else
        cout<<max(dp[n][t],-1)<<endl;
    return 0;
}

           

繼續閱讀