HDU4501：小明系列故事——买年货(三重背包)

5 1 6 1
4 3 3
0 3 2
2 3 3
3 3 2
1 0 2
4 2 5 0
0 1 0
4 4 1
3 3 4
3 4 4

12
4

很明显的背包，只是有三个取舍方法，所以开三维。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
    int a,b,w;
} s[200];

int dp[10][200][200];

int main()
{
    int n,v1,v2,k,i,j,x,y,z;
    while(~scanf("%d%d%d%d",&n,&v1,&v2,&k))
    {
        for(i = 1; i<=n; i++)
            scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].w);
        memset(dp,0,sizeof(dp));
        for(i = 1; i<=n; i++)
        {
            for(x = k; x>=0; x--)
            {
                for(y = v1; y>=0; y--)
                {
                    for(z = v2; z>=0; z--)
                    {
                        int tem = 0;
                        if(x-1>=0)
                            tem = max(tem,dp[x-1][y][z]+s[i].w);
                        if(y-s[i].a>=0)
                            tem = max(tem,dp[x][y-s[i].a][z]+s[i].w);
                        if(z-s[i].b>=0)
                            tem = max(tem,dp[x][y][z-s[i].b]+s[i].w);
                            dp[x][y][z] = max(dp[x][y][z],tem);
                    }
                }
            }
        }
        printf("%d\n",dp[k][v1][v2]);
    }

    return 0;
}

HDU4501：小明系列故事——买年货(三重背包),布布扣,bubuko.com

HDU4501：小明系列故事——买年货(三重背包)

原文：http://blog.csdn.net/libin56842/article/details/20001741