Tanky WooRSS

HDOJ 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

31 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=2191

多重背包问题:

// Tanky Woo
// HDOJ 2191

#include 
using namespace std;

int nCases;
int nValue, nKind;
int value[105], weight[105], bag[105];
int nMultiplePack[105];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &nCases;);
    while(nCases--)
    {
        memset(nMultiplePack, 0, sizeof(nMultiplePack));
        scanf("%d %d", &nValue;, &nKind;);
        for(int i=0; i=value[i]; --k)
                    if(nMultiplePack[k] < nMultiplePack[k-value[i]]+weight[i])
                        nMultiplePack[k] = nMultiplePack[k-value[i]] + weight[i];
        printf("%d\n", nMultiplePack[nValue]);

    }
    return 0;
}