【多重背包】二进制转换/ 其实有区别的--不全懂,会不放心的

2024-02-07 20:38

本文主要是介绍【多重背包】二进制转换/ 其实有区别的--不全懂,会不放心的,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

占坑。。。

https://blog.csdn.net/qinzhenhua100/article/details/40350219

啊首先二进制这个,比如7可以化成1  10 100  完美表示。。

6可以是1 10 11(1 2 3  注意是从小到大加  完美表示。。)

多重背包其实就是拆成一个一个去做,由于有些麻烦所有就用二进制代替了,反正组成起来都一样

哇,看了霜雪千年大大的文章(感谢我谷((())))

非常清楚!!!

这人将来一定适合去当老师!!1

https://www.cnblogs.com/acgoto/p/8523258.html

 

关于此题:

代码:

            //那么这个题特殊化到没有重量 并且个数已经先天给好了就是2的c次方减一  
            // 首先 一定都是2的次方减一的话 我们知道可以是直接   01  10  100 。。这种的(所以直接*2就可以了)
            // 其次  价值是v  那么就是2*v  4*v  8*v的组合都可以达到
            //w[i]里面就装的是新转化过之后的体积。
 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
int t,n,q,cnt,x,y,num,c[22],val[500],s;LL dp[10005];
int main(){for(int i=0;i<21;++i)c[i]=(1<<i)-1;while(~scanf("%d",&t)){while(t--){memset(dp,0,sizeof(dp));dp[0]=1;cnt=0;scanf("%d%d",&n,&q);for(int i=1;i<=n;++i){scanf("%d%d",&x,&y),num=c[y];for(int d=1;d<=num;num-=d,d<<=1)val[cnt++]=x*d;if(num>0)val[cnt++]=x*num;}for(int i=0;i<cnt;++i){for(int j=10000;j>=val[i];--j)dp[j]=(dp[j]+dp[j-val[i]])%mod;}while(q--){scanf("%d",&s);printf("%lld\n",dp[s]);}}}return 0;
}

关键代码(雾)

 for(int i=0;i<cnt;++i){
                for(int j=10000;j>=val[i];--j)
                    dp[j]=(dp[j]+dp[j-val[i]])%mod;
            }

 

 

另外,HDU1284  钱币-------------

-----------没有博客园账号,悄咪咪转一下,给出链接 https://www.cnblogs.com/acgoto/p/8523258.html

这个赛时看了,但是这位小老弟怎么回事写的这么简单……………………

以下为复制

Problem Description

在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input

每行只有一个正整数N,N小于32768。

Output

对应每个输入,输出兑换方法数。

Sample Input

2934

12553

Sample Output

718831

13137761

解题思路:这道题可以当做数学题来做。假设某种方案要使用i枚3分硬币(i∈[0,n/3]),那么剩下的就有n-3*i分需要用2分和1分补全。对于2分硬币的个数,可能使用0,1,·····(n-3*i)/2枚,剩下的全都用1分硬币即可。也就是说当使用i枚3分硬币时,就会产生出{(n-3*i)/2+1}*1=(n-3*i)/2+1种方案,那么只要枚举i,将所有方案数相加即可。

-----自己想了一下,的确是,可能使用1是一种,2是一种,……  一直到(。。x)个,大概是因为只有abc三个吧。。。还真爽-。-  只不过别忘记那个0  就是全是1的时候--------

AC代码一:

复制代码

 1 #include<bits/stdc++.h>2 using namespace std;3 int main(){4     int sum,n;5     while(cin>>n){6         sum=0;7         for(int i=0;i*3<=n;++i)8             sum+=(n-i*3)/2+1;9         cout<<sum<<endl;
10     }
11     return 0;
12 }

复制代码

 AC代码二:考虑dp,dp[j]表示用若干个硬币组成钱j的方案数,易得状态转移方程为:dp[j]+=dp[j-i](j>=i),意思是当前币值是i,那么在组成钱j的基础上还可以这样增加新的方案数:用之前的j-i分再和当前i分组成钱j即增加了dp[j-i]*1这么多的方案数。举个栗子:现将3分钱兑换成硬币的所有方案数有①1+1+1=3--->1种;②去掉2枚1分换成1枚2分的硬币1+2=3,那么增加了之前的1种方案数,现共有2种方案数(dp[3]+=dp[3-2]);③还有一种就是用1枚3分的硬币替换3枚1分的硬币3+0=3,定义组成0钱的方案数为1种,那么此时也增加1种方案数(dp[3]+=dp[3-3]),所以组成3分钱共有3种方案数。注意:初始化dp数组全为0,定义dp[0]=1,因为组成钱0(事实上钱0是由钱i-i=0即i=i这种情况得来的)也算一种方案数,然后对于每种币值,从i~最大35000枚举更新累加对应组成钱j的方案数即可。

----------------------自己又想了一下,这个dp理论上说应该和顺序mei有关系啊。

----------------------即使好几个i是一样的,那也是多了一种方案,因为算作的是不同的物品。……

比如,倘若3元兑换,有1种。(1个3)此时dp[0]=1   dp[1]=dp[2]=0

然后1元,dp[1]=1  dp[2]=1  (自己的状态,加上没带i之前的状态/i是新的,即,虽然新来的服务员名字和原来的一样都被叫做了服务员1号但是他们相貌其实是不相同的。。呈现在纸上的只有那个名号。。 他们还是不同的呀)

dp[3]=dp[3]+dp[2]=2(一个是自己的,一个是全1组成的)

然后2 ,dp[1]----  dp[2]=dp[2]+dp[0] (用完了2和之前1组成的那个2)

dp[3]=dp[0]+dp[3]=3... 没有疑问了

 1 #include<bits/stdc++.h>2 using namespace std;3 int main(){4     int n,dp[35000]={1};5     for(int i=1;i<=3;++i)//币值6         for(int j=i;j<35000;++j)//钱j7             dp[j]+=dp[j-i];8     while(cin>>n){cout<<dp[n]<<endl;}9     return 0;
10 }

-------------------

dp这个也很简单,像背包一样,从小到大装,组成方式啊什么的

关键代码。。。

 for(int i=0;i<cnt;++i){
                for(int j=10000;j>=val[i];--j)
                    dp[j]=(dp[j]+dp[j-val[i]])%mod;
        }

 

还有。。。要注意。。。。。。它们是从0转化而来的,所以dp[0]=1 

见过很多次了。。题目里→_→

 

讲道理嘛,下面这样写也可也

https://blog.csdn.net/tianyizhicheng/article/details/82716691  

---------------------------

好了,恭喜我又突破一个境界,看懂了不够,你要搞懂每一个细节。。。那些执行力不够/意志力不够/在很多情况下体现出自卑的人,常常觉得取得了一定的成就就可以了(其实你不写根本 就是理解 的不深刻嘛)(咦谁给我搞成中文标点输入法了。。)恭喜我 继续解锁一个成就  在大人刷抖音小孩玩滑梯放着流行歌曲的kfc比在家效率高写了this。。。。。

   for(int i=1;i<=n;++i){scanf("%d%d",&x,&y),num=c[y];for(int d=1;d<=num;num-=d,d<<=1)val[cnt++]=x*d;//其实可以不必这样,因为给的是2^x-1 肯定除尽。。  可以直接*2 当然这样子写最安全的没错了。。 记得下面这句↓
//原理呢就是分出1减去1分出2进去2 下一个该分4了啊不够了我糖糖一个6只有3分给你  不用怕 你把3拿走吧(就是下面这句剩余价值--虽然本题应该还是用不到)if(num>0)val[cnt++]=x*num;}
// 嘛。物品是这样的,从第一个开始跑i,我们知道;其次,背包要倒着写,最后大于val[x],因为不是完全背包,所以只能加一次
// val这里只要把V乘起来当做一起扩大就可以了。。for(int i=0;i<cnt;++i){for(int j=10000;j>=val[i];--j)dp[j]=(dp[j]+dp[j-val[i]])%mod;}

 

这篇关于【多重背包】二进制转换/ 其实有区别的--不全懂,会不放心的的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/688859

相关文章

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

利用Python脚本实现批量将图片转换为WebP格式

《利用Python脚本实现批量将图片转换为WebP格式》Python语言的简洁语法和库支持使其成为图像处理的理想选择,本文将介绍如何利用Python实现批量将图片转换为WebP格式的脚本,WebP作为... 目录简介1. python在图像处理中的应用2. WebP格式的原理和优势2.1 WebP格式与传统

Before和BeforeClass的区别及说明

《Before和BeforeClass的区别及说明》:本文主要介绍Before和BeforeClass的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Before和BeforeClass的区别一个简单的例子当运行这个测试类时总结Before和Befor

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

在Java中将XLS转换为XLSX的实现方案

《在Java中将XLS转换为XLSX的实现方案》在本文中,我们将探讨传统ExcelXLS格式与现代XLSX格式的结构差异,并为Java开发者提供转换方案,通过了解底层原理、性能优势及实用工具,您将掌握... 目录为什么升级XLS到XLSX值得投入?实际转换过程解析推荐技术方案对比Apache POI实现编程

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio