解题思路:
可以用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.2 (Java代码)浏览:638 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:692 |
剪刀石头布 (C语言代码)浏览:754 |
水仙花 (C语言代码)浏览:1056 |
矩阵加法 (C语言代码)浏览:1723 |
大家好,我是验题君浏览:577 |
C二级辅导-分段函数 (C语言代码)浏览:601 |
淘淘的名单 (C语言代码)浏览:1229 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:513 |