Aimee

一道非常水的分组背包求方案数

字典序这个东西要谨慎处理

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int dp[20][20];
int ma[20][20];
struct fr{
    int i;
}fr[20][20]; 
void dfs(int x,int y){
    if(x==0){
        return ;
    }
    dfs(x-1,fr[x][y].i);
    printf("%d %dn",x,y-fr[x][y].i); 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&ma[i][j]);
        }
    } 
    for(int i=1;i<=n;++i){
        for(int j=m;j>=1;--j){
            for(int z=0;z<=j;++z){
                if(dp[i-1][j-z]+ma[i][z]>=dp[i][j]){
                    dp[i][j]=dp[i-1][j-z]+ma[i][z];
                    fr[i][j].i=j-z;
                }
            }
        }
    }
    cout<<dp[n][m]<<endl;
    dfs(n,m); 
    return 0;
}