首页 > 其他分享 >蛮力法解01背包问题

蛮力法解01背包问题

时间:2023-05-01 22:15:35浏览次数:32  
标签:10 01 cout int 蛮力 物品 法解 thingsCount

#include <iostream>
using namespace std;

struct thing {
    int weight;//物品重量
    int value;//物品价值
    int number;//物品序号
};

thing things[10];//假设最多有10个物品

int thingsCount;//物品数量
int bagSize;//背包容量
int maxTotalValue;//最大总重量
int currentWeight;//当前重量
int currentValue;//当前价值
int currentPath[10];//存储当前路径
int bestPath[10];//存储最优路径

int bruteForce(int number) {//蛮力法,参数为物品序号
    if (number == thingsCount) {//最内层函数的返回条件:当已经遍历到最后一个物品时
        if (currentValue > maxTotalValue && currentWeight <= bagSize) {//若当前重量更大,只有当前容量小于背包容量才可以更新
            maxTotalValue = currentValue;
            for (int i = 0; i < number; i++) {
                bestPath[i] = currentPath[i];//将当前路径用最优路径数组保存
            }
        }
        return maxTotalValue;//递归到叶结点,返回遍历该路径后的当前最大总重量
    }
    //序号为number+1的物品装入背包的情况
    currentWeight += things[number].weight;
    currentValue += things[number].value;
    currentPath[number] = 1;
    bruteForce(number + 1);//向下递归

    //序号为number+1的物品不装入背包的情况
    currentWeight -= things[number].weight;
    currentValue -= things[number].value;
    currentPath[number] = 0;
    bruteForce(number + 1);//向下递归

    //当装入和不装入该物品的情况都遍历完后,返回当前得到的最大总重量
    return maxTotalValue;
}

int main() {
    //初始化物品数、背包容量和物品数组
    cout << "请输入物品数:";
    cin >> thingsCount;
    cout << "请输入背包容量:";
    cin >> bagSize;
    for (int i = 0; i < thingsCount; i++) {
        cout << "请输入序号为" << i + 1 << "的物品的重量和价值: ";
        cin >> things[i].weight >> things[i].value;
    }

    //蛮力法计算最优组合
    maxTotalValue = bruteForce(0);//0作为参数传入,对应递归的起点
    cout << endl;
    cout << "========蛮力法得最优解如下========"<<endl;
    cout << "背包可以装入的最大容量为:" << maxTotalValue << endl;

    //输出最优路径(最大容量选取的物品序号)
    cout << "选取了序号为:";
    for (int i = 0; i < thingsCount; i++) {
        if (bestPath[i])
            cout << i + 1 << " ";
    }
    cout << "的物品装入背包" << endl;
    system("pause");
    return 0;
}

//请输入物品数:4
//请输入背包容量:10
//请输入序号为1的物品的重量和价值 : 7 42
//请输入序号为2的物品的重量和价值 : 3 12
//请输入序号为3的物品的重量和价值 : 4 40
//请输入序号为4的物品的重量和价值 : 5 25

 

标签:10,01,cout,int,蛮力,物品,法解,thingsCount
From: https://www.cnblogs.com/Jocelynn/p/17367077.html

相关文章

  • 回溯法解决图着色问题
     #include<iostream>usingnamespacestd;intG[50][50];//保存无向图intcolor[50];//存放每个点的颜色intsum=0;//需要的颜色总数intmins=999999;//需要的最少的颜色数intN;//点的总个数//检查点第i+1个点是否能放颜色cboolcheck(inti,......
  • 回溯法解决01背包问题
    #include<iostream>usingnamespacestd;structthing{intweight;//物品重量intvalue;//物品价值intnumber;//物品数量};thingthings[10];//假设最多有10个物品intthingsCount;//物品数量intbagSize;//背包容量intmaxTotalValue;//最大总重量......
  • 回溯法解n皇后问题
    #include<iostream>usingnamespacestd;#defineMAX21intarr[MAX];//arr[i]=k,表示在第i行的第k个位置放置一个皇后intsum;//计数解的个数intn;//记录几行几列boolcmp(introw,intcol){//当前行和列for(inti=1;i<row;i++){if(col==ar......
  • 摄影-230501
    ......
  • 回溯法解工作分配问题
    #include<iostream>usingnamespacestd;inta[100][100],sum=0,minn=2147483647,i,j,n;intb[100];voiddfs(intdep){intr;for(r=1;r<=n;++r)//dep表示第几个人,r表示工作if(!b[r])//如果第r件工作没有被选择{......
  • 2023-05-01:给你一个整数 n , 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1
    2023-05-01:给你一个整数n,请你在无限的整数序列[1,2,3,4,5,6,7,8,9,10,11,...]中找出并返回第n位上的数字。1<=n<=2^31-1。输入:n=11输出:0解释:第11位数字在序列1,2,3,4,5,6,7,8,9,10,11,...里是0,它是10的一部分。答案2023-05-01:该......
  • 分支限界法解01背包问题
    #include<iostream>usingnamespacestd;#defineMAX100structNode{intisVisit;//记录节点是否被扩展doublew;doublev;intlevel;//记录节点所在的层次doubleub;//上界Node*parent;//父节点};doublemaxValue=0;Node*PT[MAX......
  • 分支限界法解TSP问题
    #include<iostream>#include<queue>#defineINF1e7#defineMAX100usingnamespacestd;intm[MAX][MAX];//存储城市间的代价intbestPath[MAX];//存储最优路径intbestCost=1e7;//存储最小代价intcityNumber;//城市数目//排列树的节点定义structNode{......
  • P5336 [THUSC2016]成绩单
    题意:期末考试结束了,班主任L老师要将成绩单分发到每位同学手中。L老师共有\(n\)份成绩单,按照编号从\(1\)到\(n\)的顺序叠放在桌子上,其中编号为\(i\)的的成绩单分数为\(W_i\)。成绩单是按照批次发放的。发放成绩单时,L老师会从当前的一叠成绩单中抽取连续的一段,让这......
  • 2023-05-01:给你一个整数 n , 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1
    2023-05-01:给你一个整数n,请你在无限的整数序列[1,2,3,4,5,6,7,8,9,10,11,...]中找出并返回第n位上的数字。1<=n<=2^31-1。输入:n=11输出:0解释:第11位数字在序列1,2,3,4,5,6,7,8,9,10,11,...里是0,它是10的一部分。答案2023-05-01:......