$$\color{Red}{背包问题求具体方案:java带思路}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围

0 < N V ≤ 1000

0 < vi wi ≤ 1000

输入样例：

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

证明

f[i][j] = Math.max(f[i-1][j], f[i-1][j - v[i]] + w[i])
背包的问题的值的动态规划可以看成一个图的传递，最终的节点连接于之前的两个节点的最大值，然后找寻最佳方案相当于求最短路

那么如果找寻字典序最小的方案，导致我们需要优先在能选更小序号的物品的情况下，先选更小序号的物品，这就决定我们找寻最佳方案的时候，需要正序遍历选取物品，那么我们的动态规划f[i][j]显然应该更改为倒序生成。之前的背包问题，我们的f[i][j]代表第一个物品到第i个物品可选，而为了优先算出排除靠前的方案，我们需要更改为f[i][j]为第i个到第n个物品可选。此时最后答案为f[1][m]，那么就需要倒序遍历i。

f[i][j] = Math.max(f[i+1][j], f[i+1][j - v[i]] + w[i])

此时我们就可以正序去找寻字典序最小最佳方案，正序遍历每个物品，当背包容量可以选取，并且刚好发现最佳方案中是可以选取的，那就选取，并减去容量，进一步判断下一个物品

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, n, m;
    static int[][] f = new int[N][N];
    static int [] v = new int[N];
    static int [] w = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] str1 = br.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for (int i = 1; i <= n; i++) {
            String[] str2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(str2[0]);
            w[i] = Integer.parseInt(str2[1]);
        }
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i + 1][j];
                if (j >= v[i])
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - v[i]] + w[i]);
            }
        }
        //f[1][m]为最终答案
        for (int i = 1, j = m; i <= n; i++) {
            if(j >= v[i] && f[i][j] == f[i+1][j - v[i]] + w[i]){
                System.out.print(i + " ");
                j -= v[i];
            }
        }
    }
}