砝码称重
本文最后更新于 204 天前,其中的信息可能已经有所发展或是发生改变。

砝码称重

你有一架天平和 �N 个砝码,这 �N 个砝码重量依次是 �1,�2,⋅⋅⋅,��W1,W2,⋅⋅⋅,W**N

请你计算一共可以称出多少种不同的重量? 注意砝码可以放在天平两边。

第一种方法:

利用set集合

 import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Set<Integer> set = new HashSet<>();
int n = scan.nextInt();
int[] fama = new int[n];
for (int i = 0; i < n; i++) {
fama[i] = scan.nextInt();
}
//初始化set集合,放入0
set.add(0);
for (int i = 0; i < n; i++) {
//将set集合转化为list集合
List<Integer> list = new ArrayList<>(set);
for (int k : list) {
//将新的砝码与set集合的元素进行加减操作,得出新的砝码秤重
set.add(k + fama[i]);
set.add(Math.abs(k - fama[i]));
}
}
//移除0元素
set.remove((Object)0);
//输出set集合大小,也就是秤重方案数
System.out.println(set.size());
scan.close();
}
}

第二种方法:

动态规划

  Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int number[]=new int [n+1];
int sum=0;
for(int i=1;i<=n;i++){
number[i]=scan.nextInt();
sum+=number[i];
}
int dp[][]=new int[n+1][sum+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
dp[i][j]=dp[i-1][j];//继承i-1个砝码的性质
if(dp[i][j]==0){
if(j==number[i]){
dp[i][j]=1;
}
else if(j>number[i]){
dp[i][j]=dp[i-1][j-number[i]];
}
else dp[i][j]=dp[i-1][number[i]-j];
}
}
}
int count=0;
for(int i=1;i<=sum;i++){
if(dp[n][i]!=0){
count++;
}
}
System.out.println(count);
}//最终状态,有三个砝码可以称出的重量首先继承有两个砝码继承的重量,在两个砝码基础上,增加一个砝码,又可以称出新的重量
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 0;// 统计能配出的个数
int[] w = new int[101];
boolean[][] dp = new boolean[101][100001];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long sum = 0L;
for (int i = 1; i <= n; i++) {
w[i] = sc.nextInt();// 每个砝码的重量
sum += w[i];// 砝码最大重量
}
for (int i = 1; i <= n; i++) {// 有多少个砝码
for (int j = 1; j <= sum; j++) {// 砝码最大重量
if (j == w[i]) {// 能称出砝码的质量就直接赋值为1说明可以称
dp[i][j] = true;
} else {
// 分为三种情况1.dp[i-1][j]如果上一次的砝码是1说明可以称出这个重量,我们直接复制下来就行了
// 2.dp[i-1][abs(j-w[i])]表示上一次称砝码放天平左边能不能配出这个重量
// 3.dp[i-1][j+w[i]]表示上一次称砝码放天平右边能不能配出这个重量
// 以上三种情况满足一种就说明此重量可以配出
dp[i][j] = dp[i - 1][j] || dp[i - 1][Math.abs(j - w[i])] || dp[i - 1][j + w[i]];
}
}
}
for (int i = 1; i <= sum; i++) {
// System.out.print(dp[n][i] + " ");
if (dp[n][i]) {
count++;
}
}
System.out.println(count);
sc.close();
}
}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇