背包问题之求具体方案数

题库

package com.zhang.reflection.面试.算法模版.背包问题模版;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
 * 技巧： 如果从需要求字典序最小， dp求解从后往前求
 * 即可从前往后推方案。
 * 求解出来dp[1][m]就是最大价值
 *有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
 *
 * 第 i 件物品的体积是 vi，价值是 wi。
 *
 * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 *
 * 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
 *
 * 输入格式
 * 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
 *
 * 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
 *
 * 输出格式
 * 输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
 *
 * 物品编号范围是 1…N。
 * 输入：
 * 4 5
 * 1 2
 * 2 4
 * 3 4
 * 4 6
 * 输出：
 * 1 4
 */
public class 求具体方案 {
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 1010, V = 1010;
    static int[] w = new int[N], v = new int[N];
    static int[][] dp = new int[N][V];
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        Scanner sc=new Scanner(System.in);
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        for(int i = 1; i <= n; i++){
            ss = read.readLine().split(" ");
            v[i] = Integer.valueOf(ss[0]);
            w[i] = Integer.valueOf(ss[1]);
        }

        for(int i = n; i >= 1; i--){
            for(int j = 0; j <= m; j++){
                //不选
                dp[i][j] = dp[i + 1][j];
                if(j - v[i] >= 0){
                    //选
                    if(dp[i + 1][j -v[i]] + w[i] > dp[i][j]){
                        dp[i][j] = dp[i + 1][j -v[i]] + w[i];
                    }
                }
            }
        }
        List<Integer> list = new ArrayList();
        int curV = m; //当前最大体积
        for(int i = 1; i <= n; i++){
            //字典序最小，从小到大遍历，能选则选
            if(curV - v[i] >= 0 && dp[i][curV] == dp[i + 1][curV - v[i]] + w[i]){
                list.add(i);
                curV -= v[i];   //选了后，最大体积就要减少v[i];
            }
        }
        for(int i = 0; i < list.size(); i++){
            System.out.print(list.get(i) + " ");
        }
    }
}