程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3535 分組背包+混合背包

hdu 3535 分組背包+混合背包

編輯:C++入門知識

/* 題意:n組數據,容積為v,temp為種類,0類至少選一個,1類至多選一個,2自由選擇,求最大價值
分組混合背包,分別確定每一組的狀態,
種類0和2時,狀態轉移方程相同,只是初始化不同,
*/
#include 
#include 
#include 
using namespace std;
#define INF -999999
int dp[105][105];
int main()
{
    int n,v;
    while(scanf("%d%d",&n,&v)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int i,j,m,temp;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&m,&temp);
            int cost[105],weight[105];
            for(j=1;j<=m;j++)
            scanf("%d%d",&cost[j],&weight[j]);
            if(temp==0)
            {
                int k;
                for(j=0;j<=v;j++)
                dp[i][j]=INF;
                for(j=1;j<=m;j++)
                    for(k=v;k>=cost[j];k--)
                   dp[i][k]=max(dp[i][k],max(dp[i-1][k-cost[j]],dp[i][k-cost[j]])+weight[j]);
            }
            else if(temp==1)
            {
                int k;
                 for(j=0;j<=v;j++)
                    dp[i][j]=dp[i-1][j];
                for(j=1;j<=m;j++)
                    for(k=cost[j];k<=v;k++)
                    dp[i][k]=max(dp[i][k],dp[i-1][k-cost[j]]+weight[j]);
            }
            else  //01背包
            {
                int k;
                 for(j=0;j<=v;j++)
                    dp[i][j]=dp[i-1][j];
                for(j=1;j<=m;j++)
                    for(k=v;k>=cost[j];k--)
                        dp[i][k]=max(dp[i][k],max(dp[i-1][k-cost[j]],dp[i][k-cost[j]])+weight[j]);
            }
        }
        dp[n][v]=max(dp[n][v],-1);
        printf("%d\n",dp[n][v]);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved