f[i][j]状态表示:前i组中选 总台数小于等于 j的情况
状态计算:
从第i组中:
选第0个。f[i - 1][j];
选第一个.f[i - 1][j - w[1]] + v[1];
......
而此题的分组就是按照公司进行分组,每组中的各个物品体积就是此种物品选择的个数,价值就是对应的输入的价值。
而求具体方案对应 题目”背包问题求具体方案”
链接: https://www.acwing.com/file_system/file/content/whole/index/content/2245984/
此题求具体方案为它满足条件的任意一种方案都行,而无需最小字典序
而求具体方案就是通过最后一个定下的物品,逆推回去,推出前面物品
代码实现:
# include <iostream>
using namespace std;
const int N = 15,M = 20;
int n,m;
int f[N][M];
int v[N][M];
int way[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
scanf("%d",&v[i][j]);
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 0 ; j <= m ; j++)
{
for(int k = 0 ; k <= j ; k++)
{
f[i][j] = max(f[i][j],f[i - 1][j - k] + v[i][k]);
}
}
}
printf("%d\n",f[n][m]);
int temp = m;
for(int i = n ; i >= 1 ; i--)
{
for(int k = 0 ; k <= temp ; k++)
{
if(f[i][temp] == f[i - 1][temp - k] + v[i][k])
{
way[i] = k;
temp -= k;
break;
}
}
}
for(int i = 1 ; i <= n ; i++)
{
printf("%d %d\n",i,way[i]);
}
return 0;
}