Blog·Tanky WooABOUTRSS

HDOJ 2602 Bone Collector

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

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2602

貌似是HDOJ中少数的几个01背包之一~~~很经典的题目。

// www.wutianqi.com
// Author: Tanky Woo
// HDOJ 2602
#include 
using namespace std;

int main()
{
int nCases;
int nPack, nMaxVolume;
int weight[1002], value[1002];
int record[1002];
    //freopen("input.txt", "r", stdin);
    scanf("%d", &nCases;);
    while(nCases--)
    {
        memset(record, 0, sizeof(record));
        scanf("%d %d", &nPack;, &nMaxVolume;);
        for(int i=0; i=weight[i]; --j)
            {
                if(record[j-weight[i]]+value[i] > record[j])
                    record[j] = record[j-weight[i]]+value[i];
            }
        printf("%d\n", record[nMaxVolume]);
    }
    return 0;
}