解题思路:
可以用DFS
注意事项:
1.还好数据量小,数据量大可能还是要DP做
2.天平两边都可以放砝码,和物体放在同侧相当于减
3.不能用判断当前质量是否小于零,或者当前选择砝码的质量大于物体质量来剪枝
参考代码:
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <stdio.h> #include <cctype> #define N 24 using namespace std; int weight[N + 2]; int obj[N + 2]; bool able[N + 2]; void DFS(int cur, int curWeight, const int tgtWeight, const int n, const int objNo) { if (cur > n) return; else if (curWeight == tgtWeight) { able[objNo] = true; return; } else { //砝码和物品分开放 DFS(cur + 1, curWeight + weight[cur], tgtWeight, n, objNo); //不放 DFS(cur + 1, curWeight, tgtWeight, n, objNo); //砝码和物品放一起 DFS(cur + 1, curWeight - weight[cur], tgtWeight, n, objNo); } } int main(int argc, char** argv) { int n = 0, m = 0; cin >> n >> m; for (int i = 0; i < n; i++) cin >> weight[i]; for (int i = 0; i < m; i++) cin >> obj[i]; for (int i = 0; i < m; i++) DFS(0, 0, obj[i], n, i); for (int i = 0; i < m; i++) { if (able[i] == true) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:277 |
计算质因子 (C++代码)浏览:1646 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:575 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:449 |
WU-格式化数据输出 (C++代码)浏览:1212 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:537 |
1014题解浏览:485 |
A+B for Input-Output Practice (V) (C语言代码)浏览:470 |
【亲和数】 (C语言代码)浏览:600 |
核桃的数量 (C语言代码)浏览:872 |