HDU - 2602 A - Bone Collector（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 ? InputThe 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.OutputOne integer per line representing the maximum of the total value (this number will be less than 2 31).Sample Input15 101 2 3 4 55 4 3 2 1Sample Output

14

这就是一道0-1背包问题。

dp[i][j]表示从第1到第i个骨头放入j体积背包的最大价值。

状态转移为：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-tj[i]]+jz[i])；

现在的前i个最大价值有两种可能，第一是第i个不选，则dp[i][j]为dp[i-1][j]，第二种是选第i个（前提是体积不超），那么包的体积减去tj[i],就为前i-1个的总体积，再加上第i个的价值jz[i]就是选第i个的结果。

见下代码（二维数组）：

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <cctype>
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int maxn=1000+5;

int t,N,V,jz[maxn],tj[maxn],dp[maxn][maxn];
int main ()
{
    //freopen ("in.txt","r",stdin);
    scanf ("%d",&t);
    while (t--)
    {
        scanf ("%d%d",&N,&V);
        for (int i=1;i<=N;i++)
        {
            scanf ("%d",&jz[i]);
        }
        for (int i=1;i<=N;i++)
        {
            scanf ("%d",&tj[i]);
        }
        memset(dp,0,sizeof(dp));
        for (int i=1;i<=N;i++)
        {
            for (int j=0;j<=V;j++)
            {
                if (tj[i]<=j) 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-tj[i]]+jz[i]);
                else dp[i][j]=dp[i-1][j];
            }
        }
        printf ("%d\n",dp[N][V]);
    }
    return 0;
}

其实不难发现，i这一维并没有多大的用处，浪费了我们太多空间，虽然时间复杂度不变，但减少了空间复杂度，只需要算j体积的背包能装下的最大体积就可以了。

代码如下（一维数组）

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <cctype>
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int maxn=1000+5;

int t,N,V,jz[maxn],tj[maxn],dp[maxn];
int main ()
{
    //freopen ("in.txt","r",stdin);
    scanf ("%d",&t);
    while (t--)
    {
        scanf ("%d%d",&N,&V);
        for (int i=1;i<=N;i++)
        {
            scanf ("%d",&jz[i]);
        }
        for (int i=1;i<=N;i++)
        {
            scanf ("%d",&tj[i]);
        }
        memset(dp,0,sizeof(dp));
        for (int i=1;i<=N;i++)
        {
            for (int j=V;j>=tj[i];j--)
            {
                if (dp[j]<dp[j-tj[i]]+jz[i])
                dp[j]=dp[j-tj[i]]+jz[i];
            }
        }
        printf ("%d\n",dp[V]);
    }
    return 0;
}