Bone Collector HDU - 2602【 01 背包 】

Bone Collector

 HDU - 2602 

&：自己的动态规划好差的，算法也跟不上，真是处处碰壁。于是找点简单的题看看，散散心。

背包是比较典型的题了，看了好一会的背包九讲，对比着来学了学。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[1005][1006]; // 未优化空间的做法

ll w[10005];
ll v[10005];

int main()
{
    ll t,n,m;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld", &n, &m);
        for(int i = 1; i <= n; i ++)scanf("%lld", &w[i]); 
        for(int i = 1; i <= n; i ++)scanf("%lld", &v[i]);

        for(int i = 0; i <= m; i ++) dp[0][i] = 0;  // 初始化

        for(int i = 1; i <= n; i ++)  //n个物品 这里dp[i][j]代表在体积为j的情况下装的i个物品的价值
        {
            for(int j = 0; j <= m; j ++) //背包的大小
            {
                if(j < v[i]) dp[i][j] = dp[i - 1][j]; // 如果体积小于v[i]也就i物品的体积，装不下，就是存前一个答案了

                else dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - v[i]] + w[i]); //否则，就要比较装与不装第i个物品的情况，取较大的
            }
        }
        printf("%lld\n",dp[n][m]);
    }
    return 0;
}

改成一维的：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[1005];

ll w[10005];
ll v[10005];

int main()
{
    ll t,n,m;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld", &n, &m);
        for(int i = 1; i <= n; i ++)scanf("%lld", &w[i]);
        for(int i = 1; i <= n; i ++)scanf("%lld", &v[i]);

        memset(dp,0, sizeof(dp));

        for(int i = 1; i <= n; i ++)
        {
           for(int j = m; j >= v[i]; j --)
           {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
           }
        }
        printf("%lld\n",dp[m]);
    }
    return 0;
}