题目描述

原题链接

样例

输入：

4 5
1 2
2 4
3 4
4 6

输出：
1 4

重点

• 背包DP的时候，状态转移时有两种选择，组合起来看，在分析一个best[i] [j]的解时，最大可能有3种情况
• 第i个物品选
• 第i个物品不选
• 第i个物品选或不选都可以

再回到这道题

• 如果是传统的做法，最后求出的最优解在 best[N] [V] ，回溯时，无法优先选择编号小的物品（因为是不确定的情况，编号大的物品能选也能不选时，没有确定的规则该选还是不该选，能够推到最后选到小的物品，此时就应该保存全部的选择，再选字典序小的）
• 如果DP时是考虑编号N，N-1，....，1个物品，最后求出的最优解在best[1] [V] (=best[N] [V] ); 在回朔时，我们在编号小的物品能选也能不选时，贪心的选择就好了。这就是为什么这一题要倒着做DP的根本原因

package codefortopic.PackPro;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PackSpecificScheme {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[][] best = new int[N + 2][V + 1];
        int[] v = new int[N + 2];
        int[] w = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            if (i != N) in.nextLine();
        }
        for (int i = N; i >= 1; i--) {
            for (int j = 0; j <= V; j++) {
                if (j >= v[i]) //开始粗心写成 >了
                    best[i][j] = Math.max(best[i + 1][j], best[i + 1][j - v[i]] + w[i]);
                else best[i][j] = best[i + 1][j];
            }
        }
        //best解在 best[1][V]中
        List<Integer> ans = new ArrayList<>();
        int resV = V;
        //这个找答案也很巧妙，需要依次枚举的是N，而v是跳跃的，这样完成了对二位结果数据的查找
        for (int i = 1; i <= N; i++) {

            if ( resV-v[i]>=0 && best[i][resV] == best[i + 1][resV - v[i]] + w[i]) {
                ans.add(i);
                resV -= v[i];
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i));
            if(i != ans.size()) System.out.print(" ");
        }
        System.out.println();
    }


}