HDUOJ--Bone Collector

Bone Collector

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21463    Accepted Submission(s): 8633

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input

The first line contain a integer T , the number of cases. Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 231).

Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1

Sample Output

14

Author

Teddy

Source

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

Recommend

lcy

背包问题.....一定要多练习...

代码:----

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 1005
 4 int dp[maxn],arr[maxn][2];
 5 int max(int a,int b)
 6 {
 7     return a>b?a:b;
 8 }
 9 
10 void zeroonepack(int cost ,int value,int v)
11 {
12      for(int i=v;i>=cost;i--)
13          dp[i]=max(dp[i],dp[i-cost]+value);
14 
15 }
16 int main()
17 {
18     int t,n,v ,i;
19     scanf("%d",&t);
20     while(t--)
21     {
22         scanf("%d%d",&n,&v);
23         memset(dp,0,sizeof dp);
24         for(i=0;i<n;i++)
25         {
26             scanf("%d",arr[i]+0);
27         }
28         for(i=0;i<n;i++)
29         {
30             scanf("%d",arr[i]+1);
31         }
32        for(i=0;i<n;i++)
33            zeroonepack(arr[i][1],arr[i][0],v);
34        printf("%d\n",dp[v]);
35     }
36     return 0;
37 }

 优化后代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct st
{
    int a;
    int b;
};
typedef struct st sta;
int main()
{
    int test,n,v,i,j;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&v);
     int *dp =(int *)malloc(sizeof(int)*(v+1));
     sta *stu =(sta *)malloc(sizeof(sta)*(n+1));
        for(i=0;i<n;i++)
            scanf("%d",&stu[i].a);
        for(i=0;i<n;i++)
            scanf("%d",&stu[i].b);
        for(i=0;i<=v;i++)
            dp[i]=0;

       for(i=0;i<n;i++)
       {
           for(j=v ; j>=stu[i].b ; j--)
           {
            if(dp[j]<dp[j-stu[i].b]+stu[i].a)
               dp[j]=dp[j-stu[i].b]+stu[i].a;
           }
       }
       printf("%d\n",dp[v]);
       free(dp);
       free(stu);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ---1171

http://acm.hdu.edu.cn/showproblem.php?pid=1171 Big Event in HDU Time Limit: 1000...

30060
来自专栏技术小黑屋

Build Android Packages From Command Line

A few months ago,I dealed with a task:To build a large amount of apk files. The...

13430
来自专栏ml

HDU----(4291)A Short problem(快速矩阵幂)

A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

35560
来自专栏ml

HDUOJ-----2399GPA

GPA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

36640
来自专栏ml

专题练习---(数论)莫比乌斯反演

            GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32...

377110
来自专栏数据结构与算法

POJ2409 Let it Bead(Polya定理)

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As...

11320
来自专栏小樱的经验随笔

HDU 1005 Number Sequence【多解,暴力打表,鸽巢原理】

Number Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

36270
来自专栏ml

HDUOJ----2952Counting Sheep

Counting Sheep Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

35870
来自专栏杂烩

Eclipse下Hadoop的MapReduce开发之mapreduce打包

点击next,使用默认选择,再点击next,在最下面的Main class处选择项目里的MapReduceTest

22530
来自专栏小樱的经验随笔

HDU 2504 又见GCD(最大公约数与最小公倍数变形题)

又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

30530

扫码关注云+社区

领取腾讯云代金券