注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!

C语言回溯法解决背包问题

OC/C/C++ 水墨上仙 2080次浏览 已收录 手机上查看

C语言回溯法解决背包问题

#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&nbsp278&nbsp312&nbsp710&nbsp58&nbsp415&nbsp95&nbsp278&nbsp812&nbsp1210&nbsp108&nbsp815&nbsp155&nbsp268&nbsp812&nbsp1210&nbsp108&nbsp815&nbsp155&nbsp288&nbsp812&nbsp1210&nbsp108&nbsp815&nbsp155&nbsp298&nbsp812&nbsp1210&nbsp108&nbsp815&nbsp15/


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言回溯法解决背包问题
喜欢 (0)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
加载中……