HDU 5616 Jam's balance 背包DP
2024-08-31 10:49:27
Jam's balance
Problem Description
Jim has a balance and N weights. (1≤N≤20)
The balance can only tell whether things on different side are the same weight.
Weights can be put on left side or right side arbitrarily.
Please tell whether the balance can measure an object of weight M.
The balance can only tell whether things on different side are the same weight.
Weights can be put on left side or right side arbitrarily.
Please tell whether the balance can measure an object of weight M.
Input
The first line is a integer T(1≤T≤5), means T test cases.
For each test case :
The first line is N, means the number of weights.
The second line are N number, i'th number wi(1≤wi≤100) means the i'th weight's weight is wi.
The third line is a number M. M is the weight of the object being measured.
For each test case :
The first line is N, means the number of weights.
The second line are N number, i'th number wi(1≤wi≤100) means the i'th weight's weight is wi.
The third line is a number M. M is the weight of the object being measured.
Output
You should output the "YES"or"NO".
Sample Input
1
2
1 4
3
2
4
5
2
1 4
3
2
4
5
Sample Output
NO
YES
YES
YES
YES
Hint
For the Case 1:Put the 4 weight alone
For the Case 2:Put the 4 weight and 1 weight on both side
题意:
Jam有NN个砝码和一个没有游标的天平,现在给他(1 \leq N \leq 20)(1≤N≤20)个砝码,砝码可以放左边,也可以放右边,问可不可以测出所问的重量, 问的个数为(1 \leq M \leq 100)(1≤M≤100)个.
题解:
这道题可以放左边,可以放右边,N=20N=20显然每种状态都枚举是不太现实的,因为每组砝码都可以变成很多种重量,当然也不排除有人乱搞过了这一题,其实这道题是一道贪心的思想,我们看到ww不大,所以可以用0101背包扫一次,当然这还是不够的,这只能放一边,考虑到可以放另一边,就是可以有减的关系,所以反着再背包一遍,注意要判断边界。
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
const int N = ;
int n,m,a[N+],dp[N+],sum;
void DP() {
memset(dp,,sizeof(dp));
dp[]= ;
for(int i = ; i<= n; i++) {
for(int k=;k;k--)
for(int j = sum*;j>=a[i];j--) {
dp[j]|=dp[j-a[i]];
}
}
}
int main() {
int T,x;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);sum=;
for(int i = ;i <= n; i++) scanf("%d", &a[i]),sum+=a[i];
DP();
scanf("%d", &m);
for(int i = ; i<= m; i++) {
scanf("%d", &x);
int g = x+sum&&sum+x>=&&dp[x+sum];
if(g)printf("YES\n");
else printf("NO\n");
}
}
return ;
}
最新文章
- MVC4 学习笔记 之 URL中存在编译的空格 20%20%
- redhat6修改主机名
- C#高级特性
- iOS开发--数组
- Gulp使用指南
- 导入GPUImage,实时滤镜相机,GUPImage遇到的问题解决,_OBJC_METACLASS_$_GBGPUImageView in GBGPUImageView.o
- [.Net MVC] Win7下IIS部署
- Android开发之UI的编程方式创建
- css filter详解
- JS学习中遇到的一些题目
- CSS3特效----图片动态提示效果
- 快速排序算法分析--C++版
- C++反汇编第六讲,认识C++中的Try catch语法,以及在反汇编中还原
- Nagle算法
- 利用HTP工具包开发报表
- MySQL保留字不能作为字段名使用
- 【深入Java虚拟机】二 类加载与双亲委派
- bootstrap面试题
- 分形之康托(Cantor)三分集
- 【待补充】Spark 集群模式 &;&; Spark Job 部署模式