首页 > 网易互联网8.8笔试_第2题平分物品_自己的题解记录
头像
XiaToulu
编辑于 2020-12-22 13:01
+ 关注

网易互联网8.8笔试_第2题平分物品_自己的题解记录

题目
现有n个物品,每一个物品都有一个价值,现将这些物品分给两个人,要求这两个人每一个人分到的物品价值总和相同,个数可不同,剩下的物品就需要扔掉,现想知道最少需要扔多少价值的物品才能满足要求分给两个人。

转移方程
含义解释
  1. 第i件物品不选,为dp[i-1][j];
  2. 选第i件物品,分两种情况,注意AB差值这里定义为A-B(当然B-A也可)
  • 给A,则两者差值更新为j+arr[i],由于选了,价值加上arr[i]。也就是dp[i-1][j+arr[i]] + arr[i]
  • 给B,则两者差值更新为j-arr[i],由于减法可能产生负值,而我们关注的只是差值具体差多少,是不是为0,所以取绝对值就行,同样因为选了,价值加上arr[i]。也就是dp[i-1][|j-arr[i]|] + arr[i]。
为了帮助理解这里的|j-arr[i]|,举例,现在A:5,B:2,下一件物品是4,那么如果给A更新后就是A:9,B:2,正常,但给B呢?就是A:5,B:6,差值就是-1,我们关注的是A,B差的距离,也就是1,取绝对值。
综上,状态转移方程取三者最大值。
Java代码
package wangyi;

import java.util.Scanner;

//不知道对不对,可能有一天遇到了可以验证一下
public class Test3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int t = sc.nextInt();
            int n = sc.nextInt();
            int[] arr = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int tmp = sc.nextInt();
                arr[i] = tmp;
                sum += tmp;
            }
            //定义状态,dp[i][j]为把第i个物品,分给A或者B后,AB差值为j时,各自物品总价的最大值(也就是A的总价最大值或B的总价最大值,当然如果j为0时,也就是成功平分了,A的最大值就是B的最大值)
            //第二层遍历的边界还是sum,而不是sum/2,因为遍历范围是所有可能的值,AB的差价极端情况肯定有可能是sum的,所谓穷举就是要遍历所有情况
            int[][] dp = new int[n+1][sum+1];
            //求最大值,不赋正无穷可不可以,赋0,默认。
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= sum; j++) {
                    //转移方程为 dp[i][j] = max(dp[i-1][j],dp[i-1][j+arr[i]]+arr[i],dp[i-1][|j-arr[i]|]+arr[i]);
                    dp[i][j] = Math.max(dp[i-1][j],
                                                    Math.max(dp[i-1][j+arr[i-1]]+arr[i-1],
                                                             dp[i-1][Math.abs(j-arr[i-1])]+arr[i-1]));
                }

            }
            System.out.println(dp[n][0]);

        }

    }

}
在代码中,注意,因为第一层循环,物品下标是0到n-1,为了和转移方程实际含义统一(第1个到第n个),取数组值必然写的都是arr[i-1]。
当然,还有一种方案就是,arr数组输入的时候就定义为1~n,0位置空出来。

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐