哈工程本科算法实验-0-1背包动态规划-分支限界-回溯法

哈工程本科算法实验-0-1背包（动态规划-分支限界-回溯法）【数据+代码+说明+流程图+测试用例】

#include
#include
#include
#define N 100
using namespace std;
class HeapNode
{
    public:
        float uprofitprofitweight;
        int levelx[N];
};
stack H;
float w[N]p[N];
float cwcp;
int ncbestx[100];
float Bound（int i）
{
    float cleft=c-cwb=cp;
    while（i<=n&&w[i]<=cleft）
    {
        cleft-=w[i];
        b+=p[i];
        i++;
        bestx[i]=1;
    }
    if（i<=n）  b+=p[i]/w[i]*cleft;
    return b;
}
void AddLiveNode（float upfloat cpfloat cwbool chint level）
{
    HeapNode nod;
    nod.uprofit=up;
    nod.profit=cp;
    nod.weight=cw;
    nod.level=level;
    if（level<=n）  H.push（nod）;
}
int Knap（）
{
    int i=1;
    cw=cp=0;
    float bestp=0up=Bound（1）;
    while（1）
    {
        float wt=cw+w[i];
        if（wt<=c）
        {
            if（cp+p[i]>bestp）   bestp=cp+p[i];
            AddLiveNode（upcp+p[i]cw+w[i]truei+1）;
        }
        up=Bound（i+1）;
        if（up>=bestp）
             AddLiveNode（upcpcwfalsei+1）;
        if（H.empty（））   return bestp;
        HeapNode node=H.top（）;
        H.pop（）;
        cw=node.weight;
        cp=node.profit;
        up=node.uprofit;
        i=node.level;
    }
}
int main（）
{
    printf（“输入背包容量:\n“）;
    scanf（“%d“&c）;
    while（c<0）
    {
         printf（“请输入合法数据:\n“）;
    scanf（“%d“&c）;
    }
    printf（“输入物品数量:\n“）;
    scanf（“%d“&n）;
    while（n<0）
    {
         printf（“请输入合法数据:\n“）;
    scanf（“%d“&n）;
    }
    FILE *fp;
    fp=fopen（“data1.txt““r“）;
   for（int i=1;i<=n;i++）
   {
       fscanf（fp“%f“&w[i]）;
       fscanf（fp“%f“&p[i]）;
   }
   cout<<“物品质量分别为：“;
   for（int i=1;i<=n;i++）
   {
       cout<   }
   cout<   cout<<“物品价值分别为：“;
   for（int i=1;i<=n;i++）
   {
       cout<   }
   cout<     for（int i=1;i<=n;i++）
        bestx[i]=0;
   fclose（fp）;printf（“0-1背包问题最优值:\n“）;
    printf（“%d\n“Knap（））;
    printf（“0-1背包问题最优解\n“）;
    for（int i=1;i<=n;i++）
        printf（“%d “bestx[i]）;
    printf（“\n“）;

    fp=fopen（“data2.txt““w“）;

        fprintf（fp“0-1背包问题最优值：%d\n “Knap（））;
        fprintf（fp“0-1背包问题最优解：“）;
           for（int i=1;i<=n;i++）
    fprintf（fp“%d “bestx[i]）;

    fclose（fp）;

    return 0;}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-11-26 19:26  0-1背包-分支限界\
     文件        2396  2016-12-05 21:15  0-1背包-分支限界\0-1.cpp
     文件      985740  2016-12-05 21:15  0-1背包-分支限界\0-1.exe
     文件       44071  2016-12-05 21:15  0-1背包-分支限界\0-1.o
     文件          23  2016-12-05 20:28  0-1背包-分支限界\data1.txt
     文件          52  2016-12-05 21:13  0-1背包-分支限界\data2.txt
     文件       10288  2016-12-05 21:24  0-1背包-分支限界\测试用例_.xlsx
     文件       63298  2016-12-05 21:24  0-1背包-分支限界\说明+流程图.docx
     目录           0  2018-11-26 19:26  0-1背包-动态规划\
     文件        1663  2016-12-05 18:02  0-1背包-动态规划\0-1背包.cpp
     文件      959845  2016-12-05 18:08  0-1背包-动态规划\0-1背包.exe
     文件        5227  2016-12-05 18:08  0-1背包-动态规划\0-1背包.o
     文件          15  2016-12-05 18:08  0-1背包-动态规划\data1.txt
     文件          48  2016-12-05 18:10  0-1背包-动态规划\data2.txt
     文件       10224  2016-12-05 18:12  0-1背包-动态规划\测试用例.xlsx
     文件       65140  2016-12-05 18:29  0-1背包-动态规划\说明+流程图.docx
     目录           0  2018-11-26 19:26  0-1背包-回溯法\
     文件          23  2016-12-05 20:28  0-1背包-回溯法\data1.txt
     文件          53  2016-12-05 21:02  0-1背包-回溯法\data2.txt
     文件        1583  2016-12-05 21:14  0-1背包-回溯法\回溯.cpp
     文件      959345  2016-12-05 21:02  0-1背包-回溯法\回溯.exe
     文件        3629  2016-12-05 21:02  0-1背包-回溯法\回溯.o
     文件       10285  2016-12-05 20:32  0-1背包-回溯法\测试用例_.xlsx
     文件       69362  2016-12-05 20:50  0-1背包-回溯法\说明+流程图.docx