#include
#include
#include
using namespace std;
#define MAXN 10
struct Goods_Info
{
int v;//价值
int w;//重量
double vw;//价值重量比
}goods[MAXN];
int n;
int maxValue;
bool solu[MAXN];
bool optimalSolu[MAXN];
bool Cmp(const Goods_Info a, const Goods_Info b)
{
return a.vw > b.vw;
}
//可装入一部分物品时，取得的最优价值
double Bound(int i, double v, int c)
{
//以物品的价值重量比递减将物品装入背包
while (i <= n && goods[i].w <= c)
{
v += goods[i].v;
c -= goods[i].w;
i++;
}
//将背包装满
if (i <= n) { v += (goods[i].vw * c); } return v; } void Backtrack(int k, int cv, int rc) { if (k > n)
{
if (cv > maxValue)
{
maxValue = cv;
int i;
for (i = 1; i <= n; i++)
{
optimalSolu[i] = solu[i];
}
}
}
else
{
if (goods[k].w <= rc) //当前物品能否装入背包 { solu[k] = true; Backtrack(k+1, cv+goods[k].v, rc-goods[k].w); } if (Bound(k+1, cv, rc) > maxValue) //剩余物品的最优价值是否更优
{
solu[k] = false;
Backtrack(k+1, cv, rc);
}
}
}
int main(void)
{
int c;
while (scanf(“%d%d”, &n, &c) != EOF)
{
int i;
for (i = 1; i <= n; i++)
{
scanf(“%d%d”, &goods[i].v, &goods[i].w);
goods[i].vw = (double)goods[i].v / goods[i].w;
}
//将物品按照价值重量比递减排序
sort(goods+1, goods+n+1, Cmp);
maxValue = 0;
Backtrack(1, 0, c);
printf(“%d\n”, maxValue); //最优值
/*
//最优解
printf(“value:”);
for (i = 1; i <= n; i++)
{
printf(“\t%d”, goods[i].v);
}
printf(“\nweight:”);
for (i = 1; i <= n; i++)
{
printf(“\t%d”, goods[i].w);
}
printf(“\nstatus:”);
for (i = 1; i <= n; i++)
{
printf(“\t%d”, optimalSolu[i]);
}
printf(“\n”);
*/
}
return 0;
}
/*5 278 312 710 58 415 95 278 812 1210 108 815 155 268 812 1210 108 815 155 288 812 1210 108 815 155 298 812 1210 108 815 15*/
开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言回溯法解决背包问题！
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176582.html原文链接：https://javaforall.net
