HDU-2602 Bone Collector—

首先输入一个数字代表有n个样例

接下来的三行

第一行输入n 和 v，代表n块骨头，背包体积容量为v。

第二行输入n块骨头的价值

第三行输入n块骨头的体积

问可获得最大的价值为多少

核心：关键在于dp【j】=max(dp[j],dp[j-w[i]]+v[i]) 的状态转移！！

背包最多能装下题目中所给的骨头，如体积为10的背包能装下体积分别为5和4的体积一块，

但最后其实背包还剩余了体积为1的位置没有讨论，则通过 j-- 进行剩余补充讨论。

在体积不断减小的同事每次都对目前这个这个体积（目前状态）下最多能装多少已知的骨头，

并通过对比之前的数据（上一次的状态）取较大值。即可获得该目标体积的最大值！！

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <stdio.h>

#define ll long long

using namespace std;

int a[];

int b[];

int dp[];

int main()

{

    int m,n,k,t;

    cin>>t;

    while(t--)

    {

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        memset(dp,,sizeof(dp));

        cin>>m>>n;

        for(int i=;i<=m;i++)

        {

            cin>>a[i];

        }//价值

        for(int i=;i<=m;i++)

        {

            cin>>b[i];

        }//体积

        for(int i=;i<=m;i++)

        {

            for(int j=n;j>=;j--)

            {

                if(j>=b[i])

                    dp[j] = max(dp[j],dp[j-b[i]]+a[i]);

            }

        }

        cout<<dp[n]<<endl;

    }

    return ;

}

巴特西

HDU-2602 Bone Collector——01背包

核心：关键在于dp【j】=max(dp[j],dp[j-w[i]]+v[i]) 的状态转移！！

最新文章

热门文章