Question

c语言 01背包问题 怎样才能够输出多个最优解

c语言外卖装箱问题，不考虑每个物品的价值，使装箱的物品体积最大即可，就是把背包问题中的价值替换为体积，实现体积最大化的最优解，我用回溯法写了一个程序，但是只能输出一个最优解，不能输出全部的，例如：箱子体积：10，物品数量：4，物品体积：2,3,5,10，最终输出的编号是1 2 3，我想让他同时输出第二种方案：4，要怎样做才能输出全部的最优解呢？这是我的代码：
#include <stdio.h>
#include <stdlib.h>
int n; //物品数量
int c; //箱子体积
int w[100]; //各个物品的体积
int cw = 0; //当前总物品体积
int bestp = 0; //当前最大体积
int order[100]; //物品编号
int put[100]; //设置是否装入

//回溯函数
void backtrack(int i)
{
int bound(int i);
if(i>n)
{
bestp = cw;
return;
}
if(cw+w[i]<=c)
{
cw+=w[i];
put[i]=1;
backtrack(i+1);
cw-=w[i];
}
if(bound(i+1)>bestp)
backtrack(i+1);
}

int bound(int i)
{
int leftw= c-cw;
int b = cw;
while(i<=n&&w[i]<=leftw)
{
leftw-=w[i];
b+=w[i];
i++;
}
if(i<=n)
b+=w[i]/w[i]*leftw;
return b;

}

int main()
{
int i;
printf("输入箱子的体积:");
scanf("%d",&c);
printf("输入外卖的数量:");
scanf("%d",&n);
printf("请依次输入每份外卖的体积：\n");
for(i=1;i<=n;i++)
{
printf("第%d个外卖的体积：",i);
scanf("%d",&w[i]);
order[i]=i;
}
backtrack(1);
printf("需要装入的外卖编号是：");
for(i=1;i<=n;i++)
{
if(put[i]==1)
printf("%d ",order[i]);
}
return 0;
}

Answer 1

你用这个代码求出了最大体积
再用一个函数求出所有符合这个最大体积的组合就可以了
既然这是你自己的代码，想必你是会写的
望采纳