题目
现有n个物品，每一个物品都有一个价值，现将这些物品分给两个人，要求这两个人每一个人分到的物品价值总和相同，个数可不同，剩下的物品就需要扔掉，现想知道最少需要扔多少价值的物品才能满足要求分给两个人。
转移方程
含义解释
- 第i件物品不选，为dp[i-1][j];
- 选第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]。
综上，状态转移方程取三者最大值。
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) 回帖