是一个动态规划问题，不是背包问题，背包问题的特点在于有最优的值，而且有某种限制。在这里面需要将花插入花瓶当中，由于有所有的花束在放入花瓶时必须保持其标识数的顺序这个限制。所以应该最外层是以花作为遍历，这样可以保证这个顺序。
那么动态转移方程为：dp[i][j]=max(dp[i-1][1~j-1])+val[i][j];。
关于方案如何给出，在这里采用向前一个去寻找的方式，也就是记录当前i，j下是由上一个哪个转移过来的。这样只要找到最优的那一个向上去寻找，将路径保存进栈里面最后将栈输出即可。 
#include <bits/stdc++.h>


using namespace std;

int node[100+10][100+10];
int dp[100+10][100+10];
int val[100+10][100+10];

signed main() {
    int f, v;
    cin>>f>>v;
    for (int i=1;i<=f;i++) {
        for (int j=1;j<=v;j++) {
            cin>>val[i][j];
            dp[i][j] = INT_MIN;
        }
    }
    for (int i=1;i<=f;i++) {
        for (int j=i;j<=v;j++) {
            dp[i][j] = val[i][j];
            int max_val;
            if (j==1)
                max_val = 0;
            else 
                max_val = INT_MIN;
            int max_pos;
            for (int k=1;k<j;k++) {
                if (dp[i-1][k]>max_val) {
                    max_val = dp[i-1][k];
                    max_pos = k;
                }
            }
            dp[i][j] += max_val;
            node[i][j] = max_pos;
        }
    }
    int ans = INT_MIN;
    int tar;
    for (int j=1;j<=v;j++) {
        if (dp[f][j]>ans) {
            ans = dp[f][j];
            tar = j;
        }
    }
    cout<<ans<<endl;
    stack<int> st;
    st.push(tar);
    for (int i=f;i>1;i--) {
        st.push(node[i][tar]);
        tar = node[i][tar];
    }
    for (int i=1;i<=f;i++) {
        cout<<st.top()<<" ";
        st.pop();
    }
    return 0;
}