关注
来个java版的 全ac的背包
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); int money = sc.nextInt(); List<Integer> list = new ArrayList<>(); while (sc.hasNext()) {
list.add(sc.nextInt()); } int[] cost = new int[list.size() / 2]; int[] earn = new int[list.size() / 2]; int[] chosen = new int[list.size() / 2]; for (int i = 0; i < list.size(); ++i) { if (i < list.size() / 2) {
cost[i] = list.get(i); chosen[i] = 0; } else {
earn[i - list.size() / 2] = list.get(i); }
} // d[i][j]表示前i个物品放入容量为j的背包的最大价值 // d[i][j] = max(d[i-1][j], d[i-1][j-weights[i]] + values[i]) int[][] d = new int[cost.length][money + 1]; for (int i = 0; i < d.length; ++i) { for (int j = 1; j < money + 1; ++j) { if (i == 0) { if (cost[i] <= j) {
d[i][j] = cost[i]; }
} else { if (j >= cost[i]) {
d[i][j] = Math.max(d[i - 1][j], d[i - 1][j - cost[i]] + earn[i]); } else {
d[i][j] = d[i - 1][j]; }
}
}
} int ii = cost.length - 1, jj = money; while (ii >= 0) { if (ii > 0) { if (jj-cost[ii] >= 0 && d[ii][jj] == d[ii - 1][jj - cost[ii]] + earn[ii]) {
chosen[ii] = 1; jj -= cost[ii]; }
} else { if (cost[ii] <= jj) {
chosen[ii] = 1; }
}
ii--; } boolean first = true; for (int i = 0; i < chosen.length; ++i) { if (chosen[i] == 1) { if (first) {
System.out.print(i + 1); first = false; } else {
System.out.print(" " + (i + 1)); }
}
}
}
查看原帖
点赞 评论
相关推荐
机械打工仔:还是那句话,它都这么对你了你还保护它干什么
点赞 评论 收藏
分享
05-30 00:12
江西服装学院 Java 头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端6.1W
- 2... 秋招应该侧重准备哪个部分的内容1.0W
- 3... 腾讯云智后台开发暑期面经8440
- 4... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)8152
- 5... 25届毕业现在在家呆了一个多月,没工作8152
- 6... 恋爱四年没想到过自己会出轨7992
- 7... 其实主包早就找到工作了,但还是每天都刷6303
- 8... 字节实习week6:听leader吐槽当前的应届生候选人们4908
- 9... 离开软件测试才发现外面没有雨4655
- 10... 作为实习生,我问薪无愧4631
正在热议
更多
# 应届生,你找到工作了吗 #
2117次浏览 31人参与
# 双非应该如何逆袭? #
173234次浏览 2939人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
38600次浏览 278人参与
# 简历当中有水分算不算造假? #
4074次浏览 40人参与
# 春招进度记录 #
340883次浏览 3214人参与
# 实习生的蛐蛐区 #
3456次浏览 35人参与
# 谈薪时HR压价该怎么应对 #
205775次浏览 3177人参与
# 百度秋招提前批进度 #
105132次浏览 1123人参与
# 三一集团提前批进度交流 #
22187次浏览 138人参与
# 毕业旅行去哪玩儿 #
7849次浏览 123人参与
# 双非有机会进大厂吗 #
433932次浏览 4375人参与
# 正在春招的你,也参与了去年秋招吗? #
308661次浏览 2523人参与
# 非技术岗投递进展 #
144424次浏览 1264人参与
# 百度求职进展汇总 #
406260次浏览 4718人参与
# 上班到公司第一件事做什么? #
60426次浏览 521人参与
# 秋招盘点:机械人值得去的企业 #
71934次浏览 670人参与
# 材料进Fab厂真的劝退吗? #
43156次浏览 184人参与
# 我的OC时间线 #
814674次浏览 7748人参与
# 百度工作体验 #
229691次浏览 2010人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
116083次浏览 1133人参与
# 如果可以,你希望哪个公司来捞你 #
96613次浏览 397人参与