HDOJ2602——01背包问题

Mogician_Jeff Nov 16, 2017

HDOJ2602背包——动态规划(DP)

问题描述

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

Sample Output

分析

这道题是动态规划算法的经典问题——01背包问题。题目翻译过来就是给出一个固定容量的背包和n个物品，每个物品有不同的体积和价值。问如何向背包里放物品可以使价值达到最大。
之所以叫01背包，也就是说每个物品只有两种状态:放入背包/不放入背包。用动态规划的思想，应该先将问题分解成小问题，求出其状态转换方程。设f(i,j)为在i个物品，j的容量下的最优解。易得状态转换方程

`f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }`

当物品数量为i时，这第i个物品是否应该放入背包？如果这个物品本身比背包容量要大，当然不能放入背包了。如果这个物品比背包容量要小，则应该比较放入和不放入哪种价值更高。

同时，要注意边界问题。当i=1时，此时没有物品，最优解必定为0。同理，当j=0时，最优解也为0。

这道题的核心便是这个方程的推导，参考动态规划之01背包问题

实现
写出来的第一个版本因为用malloc定义数组而忘记free而MLE。发现其实并不需要动态分配数组。直接定义一个元素大小为1001的整型数组便完事。第二次提交的时候又TLE了，感觉是因为函数调用次数太多，实在无奈，去网上看了一下别人的思路。

/*我的版本，TLE了*/
#include<stdio.h>

int max(int a,int b)
{
  if(a > b) return a;
  else return b;
}
int package(int n,int v,int vol[],int val[])
{
  if(n==0) return 0;
  else if(vol[n-1] > v) return package(n-1,v,vol,val);
  else return max(package(n-1,v,vol,val),package(n-1,v-vol[n-1],vol,val)+val[n-1]);
}

int main()
{
  int count;
  int i,j,n,v,vol[1001],val[1001];  //n为物品数，v为背包容量
  scanf("%d",&count);
  while(count--)
  {
    scanf("%d %d",&n,&v);
    for(i=0;i<n;i++)
    {
      scanf("%d",&val[i]); //记录每个物品的价值
    }
    for(i=0;i<n;i++)
    {
      scanf("%d",&vol[i]);  //记录每个物品的体积
    }
    int max = 0,p;
    for(i=0;i<n+1;i++)
    {
      for(j=0;j<v+1;j++)
      {
        p = package(i,j,vol,val);
        if(p > max) max = p;
      }
    }
    printf("%d\n",max);
    /*数组清零*/
    for(i=0;i<n;i++)
    {
      val[i] = 0;
    }
    for(i=0;i<n;i++)
    {
      vol[i] = 0;
    }
  }
}

/*用循环实现*/
#include<stdio.h>
#include<string.h>
int main()
{
  int count;  //记录case的次数
  int i,j,n,v,vol[1001],val[1001],dp[1001];  //n为物品数，v为背包容量
  scanf("%d",&count);
  while(count--)
  {
    /*数组初始化*/
    memset(vol,0,sizeof(vol));
    memset(val,0,sizeof(val));
    memset(dp,0,sizeof(dp));

    scanf("%d %d",&n,&v);
    for(i=0;i<n;i++)
    {
      scanf("%d",&val[i]); //记录每个物品的价值
    }
    for(i=0;i<n;i++)
    {
      scanf("%d",&vol[i]);  //记录每个物品的体积
    }
    for(i=0;i<n;i++)  //当有i个物品时，dp的最优解。注意边界值。
    {
      for(j=v;j>=vol[i];j--)  //遍历所有背包容量大于物品大小的情况
      {
        if(dp[j] < dp[j-vol[i]] + val[i]) //在有i个物品的情况下，如果第i个物品放入背包的价值高，则放入物品
          dp[j] = dp[j-vol[i]] + val[i];
      }
    }
    printf("%d\n",dp[v]); //输出背包容量最大时的情况
  }
}

... ... ...