分组背包和背包问题求方案数的结合体,不错,实在是太不错了。
//f[i][j]:从前i组物品中选,总体积(总台数)不超过j的所有选法
#include<bits/stdc++.h>
using namespace std;
const int N = 20,M = 25;
int f[N][M],w[N][M];
int path[N];//用来存储具体方案
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=0;k<=j;k++)//因为本题w[i][k(也就是0)]=0,所以上一行可以去掉
f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
}
cout<<f[n][m]<<endl;
//y总的special judge太棒啦
int j=m;//用j代表总体积,然后逐组递减,真的是太~妙~啦~
for(int i=n;i;i--)//从后往前推,看f[i][j]是由哪个状态转移而来的
for(int k=0;k<=j;k++)
if(f[i][j]==f[i-1][j-k]+w[i][k])
{
path[i]=k;
j-=k;
break;//得到一种方案之后就退出本组循环
}
for(int i=1;i<=n;i++)cout<<i<<' '<<path[i]<<endl;
return 0;
}