大疆19年校招0806笔试B卷第一题（背包问题）

同学晚上做题，我就看了看第一题，这个第一题有点像四号的第二题，但是由于游戏时间必须全部完成才能得到满意度，所以选择游戏的时候只依靠贪心算法不够了，需要用动态规划来解决问题。

题目：游戏王

小明要玩游戏，每个游戏都有它的成就值，也有玩这个游戏需要花费的时间（每个游戏必须玩完才能获得成就值）。小明总共有T的时间。求在T的时间内可以获得的最大成就值。

输入：
第一行输入case数T（0

输出：
对于每个case输出一行，成就值之和的最大值。

样例输入：
2
2 2
10 1
20 2
3 4
10 2
18 3
10 2样例输出：
20
20

题目分析

典型的01背包问题

基本思路是将该问题转化为子问题进行求解。考虑N件物品在限重M的背包下可选择的最大价值F[N][M],这个问题可以分解成两种情况来考虑：这是一个非黑即白的问题，因为一个物品只存在两种状态，放入背包和没有放入背包.

• N1不放入背包，则问题转化为F[N-1][M]，N1不放入背包，则物品数减一
• N1放入背包，问题转化为value[N1]+f[N-1][M-weight[N1]]，N1放入背包，则背包承重减少。

原问题的解取上面两种情况中的最大值。既F[N][M] = max{F[N-1][M], (F[N-1][M-weight[N1]+value[N1]))}。接下来问题又变成了求解F[N-1][M]和 F[N-1][M-weight[N1]两个子问题。然后一直类推到一个物品时。以此类推的话我们解决原始问题需要子问题的解。我们需要先计算子问题，自底向上求解。解决顺序如下表。从左到右，从上到下计算。货品的顺序不影响最后的计算结果。
采用二维数组存贮状态值，自下而上避免重复计算。更详细的可以参考01背包问题——贪心+DP

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();while (T-- > 0) {int gamenum = in.nextInt();int havedays = in.nextInt();int value[] = new int[gamenum + 1];int days[] = new int[gamenum + 1];int allvalue = 0;int alldays = 0;for (int i = 1; i <= gamenum; i++) {value[i] = in.nextInt();days[i] = in.nextInt();allvalue += value[i];alldays += days[i];}if (alldays <= havedays)System.out.println(allvalue);else {int dp[][] = new int[gamenum + 1][havedays + 1];for (int i = 0; i <= havedays; i++) {dp[0][i] = 0;}for (int i = 0; i <= gamenum; i++) {dp[i][0] = 0;}for (int i = 1; i <= gamenum; i++) {for (int j = 1; j <= havedays; j++) {if (j < days[i]) {//当背包的重量小于当前物品的重点时，则沿用上一行的value值dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - days[i]] + value[i]);}}}System.out.println(dp[gamenum][havedays]);}}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！