首页 > 其他分享 >背包问题-二进制优化

背包问题-二进制优化

时间:2023-07-01 23:45:28浏览次数:72  
标签:背包 二进制 value ## 砝码 new 优化 dp mathrm

Smiling & Weeping

                  ----不讨好所有冷漠 不辜负所有热爱

 

# [NOIP1996 提高组] 砝码称重

 

## 题目描述

 

设有 $1\mathrm{g}$、$2\mathrm{g}$、$3\mathrm{g}$、$5\mathrm{g}$、$10\mathrm{g}$、$20\mathrm{g}$ 的砝码各若干枚(其总重$ \le 1000$),可以表示成多少种重量?

 

## 输入格式

 

输入方式:$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$

 

(表示 $1\mathrm{g}$ 砝码有 $a_1$ 个,$2\mathrm{g}$ 砝码有 $a_2$ 个,…,$20\mathrm{g}$ 砝码有 $a_6$ 个)

 

## 输出格式

 

输出方式:`Total=N`

 

($N$ 表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)

 

## 样例 #1

 

### 样例输入 #1

 

```
1 1 0 0 0 0
```

 

### 样例输出 #1

 

```
Total=3
```

 

## 提示

 

**【题目来源】**

 

NOIP 1996 提高组第四题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int a[7] = {0,1,2,3,5,10,20} , num[10];
 5 ll dp[10010] , new_value[10010] , n , ans;
 6 int main()
 7 {
 8     for(int i = 1; i <= 6; i++)
 9         scanf("%d",&num[i]) , n += num[i]*a[i];
10     dp[0] = 1;
11     int n_new = 0;
12     for(int i = 1; i <= 6; i++)
13     {
14         for(int j = 1; j <= num[i]; j <<= 1)
15         {
16             num[i] -= j;
17             new_value[++n_new] = j * a[i];
18         }
19         if(num[i])
20         {
21             new_value[++n_new] = num[i] * a[i];
22         }
23     }
24     for(int i = 1; i <= n_new; i++)
25         for(int j = n; j >= 1; j--)
26             if(j >= new_value[i])
27                 dp[j] += dp[j - new_value[i]];
28     for(int i = 1; i <= n; i++)
29         if(dp[i])
30             ans++;
31     cout << "Total=" << ans << endl;
32     return 0;
33 }

其实我们可以想到,我们DP的自我滚动从n到1,是为了保证不会像dp[j+new_value[i]] += dp[j]的重复计算

我们从n到1会保证了每个只得到正确的计算次序!!!

加强理解

详见P2347 [NOIP1996 提高组] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

标签:背包,二进制,value,##,砝码,new,优化,dp,mathrm
From: https://www.cnblogs.com/smiling-weeping-zhr/p/17519830.html

相关文章

  • 【深入了解系统性能优化】「实战技术专题」全方面带你透彻探索服务优化技术方案(系统服
    调优意义系统运行缓慢,执行速度较差虽然没有对用户或公司造成实质性的损失,但它从侧面反映出系统在某些方面存在问题。可能需要对系统参数进行优化,或者对系统的设计和交互进行调整,这是后续系统性能优化的一个重要过程。我们将继续努力优化系统,以确保其高效运行和良好性能,以提升用户体......
  • 【深入了解系统性能优化】「实战技术专题」全方面带你透彻探索服务优化技术方案(系统服
    @目录调优意义计划分析流程相关分析优化分析Nginx请求服务日志将请求热度最高的接口进行优化异步调用优化方式注意要点分析调用链路追踪体系建立切面操作分析性能和数据统计存储相关的调用以及耗时信息分析信息以及相关的耗时损耗日志系统的升级和优化异步日志处理机制异常问题和......
  • 提升项目数据查询速度:从pgsql数据库性能到SQL优化的实战经验分享
    最近在项目中遇到这样一个问题,在进行数据查询的时候,特别的慢。项目的基本情况首先描述下项目的使用情况,数据库使用的是postgresql关系型数据库,主要数据存储字段data使用的类型是JSONB。data字段存储数据,这个数据是包含了不少的图元,特别是在性能测试中,加入了特别多的图元信息,最......
  • 众所周知,梯度下降法是一种基本的优化算法,不能保证全局最优,也不能保证效率。为什么它仍
    梯度下降法在深度学习中被广泛应用的原因主要有以下几点:适用性广泛:梯度下降法可以应用于各种深度学习模型,包括神经网络、卷积神经网络、循环神经网络等。而传统的凸优化算法和粒子群算法往往只适用于特定类型的优化问题。原理简单:梯度下降法的原理相对简单,易于理解和实现。......
  • 肖sir___数据库语句优化方法
        1.避免出现SELECT*FROMtable语句,要明确查出的字段。案例:好:sql= "selectpeople_name,pepole_agefrompeople";坏:sql= "select*frompeople";使用select*的话会增加解析的时间,另外会把不需要的数据也给查询出来,数据传输也是耗费时间的,比如text类型......
  • TCP TIME_WAIT 状态 及相关问题优化
    TCP是一种面向连接的可靠的传输协议,它在建立和释放连接时,需要经过一系列的握手和挥手过程。在这个过程中,会涉及到一些不同的状态,其中一个比较常见但又容易被误解的状态就是TIME_WAIT状态。本文将从以下几个方面介绍TIME_WAIT状态的原理和优化方法:TIME_WAIT状态是如何产生......
  • SAP CRM Fiori 应用后台 OData 服务性能优化的一些思路
    取一个task的attachmentheader信息(包含4个attachment)都需要0.5秒时间,太慢了。具体分析:取attachment时,会先callretrieve_task_opt取taskheader信息,消耗0.1秒。通过之前4个节点的优化经验,这个retrieve是不需要的,此时header信息已经在memory里了,直接使用即可。主要的瓶颈就......
  • 前端性能优化1
    1.NavigationTimingAPI1.unloadEventStart/end前一个页面的unload时间戳=>无前置页面时?=>值为0=>前置页面域不同=>值为02.redirectStart/end第一个http重定向发生的时间/最后一个http重定向完成的时间=>有跳转且是同域名=>否则值为03.fetchStart浏览器准备好......
  • 9.模型优化
    模型三角形数量增加增加模型三角形数量目的是使模型表面更加光滑调整三角形的位置路普细分LoopSubdivis一个三角形拆成4个loop不是循环细分如何调整细分后的三角形的位置?(为了让细分后的平面变平滑)新的细分点在路普细分中,假定两个相邻三角形中下图白色点为相邻......
  • Vue项目卡顿慢加载?这些优化技巧告诉你!
    前端开发是一个快速发展的领域,每天都会涌现出新的技术和工具。在实现功能的同时,开发人员面临着许多挑战如代码可维护性,加载时间,访问速度,构建速度等问题。这些挑战可能直接影响网站的性能和用户体验,需要采取一些优化措施来改善问题。在本文中,我们将探讨一些前端项目优化的具体措施......