前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Bone Collector HDU - 2602【 01 背包 】

Bone Collector HDU - 2602【 01 背包 】

作者头像
Lokinli
发布2023-03-09 19:19:09
1920
发布2023-03-09 19:19:09
举报
文章被收录于专栏:以终为始以终为始

Bone Collector

HDU - 2602 

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

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

代码语言:javascript
复制
#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;
}

改成一维的:

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-02-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Bone Collector
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档