dp背包问题

一开始想直接用dp[N]，但是这个题目需要输出每个被放入的物品。所以不能把二维压缩成一维，使用dp[N][N]。又因为这里需要输出字典序最小的，也就是说从前往后能放进去的就要放进去，第一个能放就放第一个，这样子倒推是从最小的下标开始输出。而按之前常规写法是从后面的物品开始放，字典序应该是最大的。

注意这里下标从1开始。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, v;
int weight[N];
int value[N];
int dp[N][N];


int main() {
    cin >> n >> v;
    for(int i = 1; i <= n; i++){
        cin >> weight[i] >> value[i];
    }


    for(int i = n; i > 0; i--){
        for(int j = 0; j <= v; j++){
            dp[i][j] = dp[i+1][j];
            if(j >= weight[i]){
                dp[i][j] = max(dp[i][j], dp[i+1][j - weight[i]] + value[i]);
            }
        }

    }

    int i = 1, j = v;
    while(i <= n){
        if(j >= weight[i] && dp[i+1][j - weight[i]] + value[i] >= dp[i+1][j]){
            printf("%d ", i);
            j -= weight[i];
            i++;
        }else{
            i++;
        }
    } 

    return 0;
}