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

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

相关文章

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

GORM中Model和Table的区别及使用

《GORM中Model和Table的区别及使用》Model和Table是两种与数据库表交互的核心方法,但它们的用途和行为存在著差异,本文主要介绍了GORM中Model和Table的区别及使用,具有一... 目录1. Model 的作用与特点1.1 核心用途1.2 行为特点1.3 示例China编程代码2. Tab

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Spring中@RestController和@Controller的使用及区别

《Spring中@RestController和@Controller的使用及区别》:本文主要介绍Spring中@RestController和@Controller的使用及区别,具有很好的参考价... 目录Spring中@RestController和@Controller使用及区别1. 基本定义2. 使

Java实现XML与JSON的互相转换详解

《Java实现XML与JSON的互相转换详解》这篇文章主要为大家详细介绍了如何使用Java实现XML与JSON的互相转换,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. XML转jsON1.1 代码目的1.2 代码实现2. JSON转XML3. JSON转XML并输出成指定的