算法描述

1. 逆序存放输入元素
2. 使用二维数组，按01背包的入门解法计算
3. 从dp[N][V]位置反推，如果最优方案可以由选取当前物品得到，那就选择当前物品，然后转到上一层。

Java 代码

import java.util.Scanner;

class Main{
    public static void main(String[] args){
        try(Scanner scanner = new Scanner(System.in)){
            int N = scanner.nextInt();
            int V = scanner.nextInt();
            Item[] goods = new Item[N];

            for(int i=N-1; i>=0; i--){ // 逆序存放
                goods[i] = new Item(scanner.nextInt(), scanner.nextInt());
            }

            int[][] dp = new int[N+1][V+1];
            for(int i=1; i<=N; i++){
                for(int j=0; j<=V; j++){
                    dp[i][j] = dp[i-1][j];
                    if(j >= goods[i-1].v){
                        dp[i][j] = Math.max(dp[i][j], goods[i-1].w + dp[i-1][j-goods[i-1].v]);
                    }
                }
            }

            int i=N, j=V;
            while(dp[i][j] > 0){
                // 下标越界检查  j-goods[i-1].v >= 0
                if(j-goods[i-1].v >= 0 && dp[i][j] == goods[i-1].w + dp[i-1][j-goods[i-1].v]){
                    System.out.print((N+1-i) + " ");
                    // 顺序不能反
                    j = j-goods[i-1].v;
                    i = i-1;
                }else{
                    i = i-1;
                }
            }
        }
    }

    private static class Item{
        public int v;
        public int w;
        public Item(int v, int w){
            this.v = v;
            this.w = w;
        }
    }

}

参考文献

dd大牛的《背包九讲》