程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3033 I love sneakers! 分組背包

HDU 3033 I love sneakers! 分組背包

編輯：C++入門知識

我是個逗比。。。真心不是搞算法的料

不太中規中矩的分組背包，分組至少選一件商品。dp[i][j] 可以由當前dp[i-1][j-c] 和 dp[ i ][j-c]更新得到。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long LL
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 1000000007
#define LM(a,b) (((ULL)(a))<<(b))
#define RM(a,b) (((ULL)(a))>>(b))

using namespace std;

int Top[12];

struct N
{
    int c,w;
}pro[12][110];

int dp[12][10011];

int main()
{
    int n,m,k;

    int u,v,w,i,j;

    while(scanf("%d %d %d",&n,&m,&k) != EOF)
    {
        memset(dp,-1,sizeof(dp));

        memset(Top,0,sizeof(Top));

        for(i = 0; i < n; ++i)
        {
            scanf("%d %d %d",&u,&v,&w);
            pro[u][Top[u]].c = v;
            pro[u][Top[u]].w = w;
            Top[u]++;
        }

        dp[0][0] = 0;

        for(i = 1;i <= k; ++i)
        {
            for(j = 0;j < Top[i]; ++j)
            {
                for(w = m-pro[i][j].c; w >= 0; w--)
                {
                    if(dp[i][w] != -1 && dp[i][w+pro[i][j].c] < dp[i][w] + pro[i][j].w)
                    {
                        dp[i][w+pro[i][j].c] = dp[i][w] + pro[i][j].w;
                    }

                    if(dp[i-1][w] != -1 && dp[i][w+pro[i][j].c] < dp[i-1][w] + pro[i][j].w)
                    {
                        dp[i][w+pro[i][j].c] = dp[i-1][w] + pro[i][j].w;
                    }
                }
            }
        }
        int Max = dp[k][0];

        for(i = 1;i <= m; ++i)
        {
            Max = max(Max,dp[k][i]);
        }

        if(Max == -1)
        {
            printf("Impossible\n");
        }
        else
        {
            printf("%d\n",Max);
        }
    }

    return 0;
}