2 条题解
-
8
我又来水题解啦~
这道题灰墙的简单（为什么难度到9）
其实就是在作业的代码上加路径存储就OK啦 附上完整代码
#include <bits/stdc++.h> using namespace std; int f[10005], a[10005], n, m; vector<int> ans[2005];//向量ans int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; memset(f,0x3f,sizeof(f));//一定要初始化！ f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= a[i]; j--)//倒着判断 { if (f[j-a[i]] + 1 < f[j]) { f[j] = f[j-a[i]]+1; ans[j] = ans[j-a[i]];//记录路径 ans[j].push_back(i); } } } for (int i = 0;i < ans[m].size();i++)//输出 { cout << ans[m][i] << " "; } return 0;//华丽的结束 }点个赞吧！
-
hetao1394742
@ 2024-4-20 10:52:35
我寻思着输出的for循环还得出个warning很不舒服，改一下，加个强制类型转换，代码如下
#include <bits/stdc++.h> using namespace std; int f[10005], a[10005], n, m; vector<int> ans[2005]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= a[i]; j--) { if (f[j - a[i]] + 1 < f[j]) { f[j] = f[j - a[i]]+1; ans[j] = ans[j - a[i]]; ans[j].push_back(i); } } } for (int i = 0; i < static_cast<int>(ans[m].size()); i++) { cout << ans[m][i] << " "; } return 0; } -
hetao10711894
@ 2024-5-5 20:23:04
😄 额……行太多了！还是别自由发挥了，按课后作业的代码做吧。👍 👍 👍 🎉️
int main() { memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= a[i]; j--) { if (f[j - a[i]] + 1 < f[j]) { f[j] = f[j - a[i]] + 1; ans[j] = ans[j - a[i]]; ans[j].push_back(i); } } } }
-
-
0
本题是在作业题的基础上，进行01背包路径存储即可。
参考代码
for (int i = 1; i <= n; i++) { for (int j = m; j >= a[i]; j--) { if (f[j - a[i]] + 1 < f[j]) { f[j] = f[j - a[i]] + 1; ans[j] = ans[j - a[i]]; ans[j].push_back(i); } } }-
hetao815606
@ 2023-10-21 10:35:21
替易云老师补全一些：
int main() { memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= a[i]; j--) { if (f[j - a[i]] + 1 < f[j]) { f[j] = f[j - a[i]] + 1; ans[j] = ans[j - a[i]]; ans[j].push_back(i); } } } } -
hetao1802625
@ 2024-5-16 13:27:18
@圣皇 大好人👍
-
hetao5761342
LV 10
@ 2023-12-25 20:03:25
- 1