网站建设所需硬件,千锋教育西安校区,好用的网站管理系统,宁波seo自然优化技术大家好 我是寸铁 希望这篇题解对你有用#xff0c;麻烦动动手指点个赞或关注#xff0c;感谢您的关注
不清楚蓝桥杯考什么的点点下方#x1f447;
考点秘籍
想背纯享模版的伙伴们点点下方#x1f447;
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不…大家好 我是寸铁 希望这篇题解对你有用麻烦动动手指点个赞或关注感谢您的关注
不清楚蓝桥杯考什么的点点下方
考点秘籍
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全第二期
蓝桥杯省一你一定不能错过的模板大全第三期
蓝桥杯省一你一定不能错过的模板大全第四期
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)
蓝桥杯上岸每日N题第一期(二)
蓝桥杯上岸每日N题第一期(三)
蓝桥杯上岸每日N题第二期(一)
蓝桥杯上岸每日N题第三期(一)
蓝桥杯上岸每日N题 第四期(最少刷题数)
蓝桥杯上岸每日N题 第五期(山)
蓝桥杯上岸每日N题 第六期(求阶乘)
蓝桥杯上岸每日N题 第七期(小猫爬山)
蓝桥杯上岸每日N题 第八期 (全球变暖)
蓝桥杯每日N题 (消灭老鼠)
蓝桥杯每日N题杨辉三角形
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句期末冲刺
想看JavaB组填空题的伙伴们点点下方
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷(模拟/枚举专题)
蓝桥杯上岸必背 (第三期 DP)
蓝桥杯上岸必背(第四期DFS)
蓝桥杯上岸必背(第五期BFS)
蓝桥杯上岸必背(第六期树与图的遍历)
蓝桥杯上岸必背(第七期 最短路算法)
蓝桥杯上岸必背(第八期 简单数论)
蓝桥杯上岸必刷(进制、数位专题)
蓝桥杯上岸考点清单 (冲刺版
蓝桥杯上岸必背模板 (纯享版
分析
有限制的选择问题(背包问题)
观察题目样例解释: 可以将物品放在两边的天平中,可以将物品的重量看作w、-w。 把物品分配在天平两边问题可以转换成从背包总容量为m的背包中选取重量为w、-w的物品的方案数。
状态表示
集合所有从前i件物品中选择且重量为j的所有方案的集合 属性集合是否非空(boolean值)
状态划分
将集合划分为3类 情况1不选当前第i件物品 情况2: 选当前第i件物品且为 w 情况3选当前第i件物品且为 -w
注意
由于可以选择-w的情况,数组下标会出现负数情况。 所以,我们需要给下标加上一个偏移量B,使数组下标不越界。
Accode
import java.util.*;
public class Main{static int N110,M200010;static int a[]new int[N];static boolean f[][]new boolean[N][M];static int BM/2;//考虑到边界数组下标不能是负数//这里加上偏移量将数组下标变为合法值public static void main(String []args) {Scanner scnew Scanner(System.in);int nsc.nextInt();int m0;for(int i1;in;i) {a[i]sc.nextInt();ma[i];}f[0][B]true;//0件物品一件都不装是一种方案//记为truefor(int i1;in;i) {//for(int j-m;jm;j) {f[i][jB]f[i-1][jB];//从前i-1个物品中选,不选第i个物品if(j-a[i]-m)f[i][jB]|f[i-1][j-a[i]B];//从前i-1个物品中选,且选了第i个物品a[i]if(ja[i]m)f[i][jB]|f[i-1][ja[i]B];//从前i-1个物品中选,且选了第i个物品-a[i] //考虑到数组下标越界,数组下标不能是负数。//需要加上偏移量B}}int res0;for(int j1;jm;j) {if(f[n][jB])res;//jB是因为砝码总重为1e5//负数情况-1e5B0//负数情况也被包含进来所以直接对f[n][jB]判断即可。//检测所有从1-i个数中体积为j的集合是否非空//非空则加上1}System.out.println(res);}
}
