蓝桥杯Java ABC组 AcWing P12 背包问题求具体方案
题目链接：
https://www.acwing.com/problem/content/12/
#记录路径
字典序最小百分之九十都可以用贪心去解决
如果要求字典序最小，就相当于要把递归改递推，让dp从n到1倒着来，这样贪心时才能找回去
倒推状态转移路径的时候，只能在分叉转移的时候，即当前物品既可以选又可以不选时，优先选
代码
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++)
cin >> v[i] >> w[i];
for(int i = n ; i >= 1 ; i --){
for(int j = 0 ; j <= m ; j++){
f[i][j] = f[i + 1][j];
if(j >= v[i])
f[i][j] = max(f[i][j],f[i + 1][j - v[i]] + w[i]);
}
}
int cur_v = m;
for(int i = 1 ; i <= n ; i++){
if(cur_v - v[i]>=0 && f[i][cur_v] == f[i + 1][cur_v - v[i]] + w[i]){
printf("%d ",i);
cur_v = cur_v - v[i];//选了第i个物品，剩余容量就要减小。
}
}
return 0;
}
原文地址：https://blog.csdn.net/qq_36992525/article/details/136933212
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！