专栏首页Zaqdt_ACMNYOJ 860 又见01背包(思维)

NYOJ 860 又见01背包(思维)

       刚一看这道题以为是01背包的裸题,TLE了一次后发现这是一道拐了个弯的裸题,题中给的物品重量范围太大了,所以我们可以换种思路,把最大价值求出来,然后在dp中用价值去存重量,然后价值从大到小遍历找出第一个不大于题中给的重量,然后输出价值即可。

AC代码:

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
int dp[MAXN];
int w[200];
int v[200];
int m,p;
int main()
{
    while(cin>>m>>p){
      int sum = 0;
    for(int i=0;i<m;i++){
      cin>>w[i]>>v[i];
      sum+=v[i];
    }
    memset(dp,MAXN,sizeof(dp));      // 要求最小值,需要都初始化为最大值
    dp[0] = 0;                       // 这个符合情况,需要单独把dp[0]初始化为0
    for(int i=0;i<m;i++){            // 01背包按重量存入dp
      for(int j=sum;j>=v[i];j--){
        dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
      }
    }
    for(int i=sum;i>=0;i--){    // 从价值最大开始往后遍历
      if(dp[i] <= p){           // 当遍历到第一个dp[i] <= p 时刚好符合题意,输出i即可
        cout<<i<<endl;
        break;
      }
    }
  }
  return 0;
}
/***
   [来源] NYOJ 860
   [题目] 又见01背包
   [大意]
      虽然是一个01背包题,但是数据范围太大,跑下来肯定会TLE所以要换种方式去做,因为要求重量不超过W的最大价值,可以
      反着求最小重量,对应的就是其最大价值。详细看代码注释。
    [输入]
      4 5
      2 3
      1 2
      3 4
      2 2
    [输出]
      7
  */

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Hiho Coder 1038 01背包(模板)

           01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci,得到的价值是Wi,求将哪些物品装入背包可使获得的价值总和最大。而...

    Ch_Zaqdt
  • POJ 2603 HDU 1963 Investment(完全背包)

            这有一篇完全背包的详解,也加了判断是否恰好装满的状态传送门(Piggy-Bank)

    Ch_Zaqdt
  • HDU 2602 Bone Collector(01背包模板题)

    Ch_Zaqdt
  • HDU-6006-Engineer Assignment

    ACM模版 描述 ? 题解 常规的状压 DPDP 套路。 给定 NN 个任务和 MM 个工程师,每个任务都有不超过三个的领域人才需求,每个工程师都有不超过两个领...

    f_zyj
  • 2559. [NOIP2016]组合数问题

    【题目描述】 【输入格式】    从文件中读入数据。    第一行有两个整数t, k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。 ...

    attack
  • Golang Leetcode 956. Tallest Billboard.go

    dp思路 dp方程的键为两个柱子之间的高度差,值为当前高度差情况下,两个柱子的最小高度 状态转移的时候有三种情况,其中后两种可以合并 最后dp[0]保存的...

    anakinsun
  • 87. [NOIP2000] 乘积最大

    ★☆   输入文件:cjzd.in   输出文件:cjzd.out 简单对比 时间限制:1 s   内存限制:128 MB   问题描述 今年是国际...

    attack
  • HDU 4283 You Are the One

    老感觉是贪心,一直没明白,我一直觉得贪心能做出来,区间DP做这个题,理解不了,索性,先放放,过两天回头再看看,刚开始从简单题开始,先做点简单题让自己理解。

    风骨散人Chiam
  • P2690 接苹果

    题目背景 USACO 题目描述 很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树(编号为1和2), 每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果,所...

    attack
  • 经典算法之动态规划

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也...

    用户3467126

扫码关注云+社区

领取腾讯云代金券