蛮力法解决01背包问题

admin管理员组

文章数量:1130349

蛮力法：设计算法求解背包问题，并编程实现。

背包问题: 

给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。

背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集。

实验：

编写程序，实现背包问题的蛮力算法。并针对以下两个实例，求出能装到背包中的价值最大的子集。要求输出：最优可行子集和该子集的最大价值。

代码实现：

#include <iostream>

int sum_v;//货物总价值
int sum_w;//货物总重量
int goodNum;//一共有多少货物
int ans;//背包中现有几个货物
int maxWeight;//背包的总容量
int r[100];//记录最后的选择的货物标号

using namespace std;
struct good
{
    int weight;
    int value;
    int flag;//记录该货物是否被挑选
}goods[100];
//更新序列，并返回最大
int record(int sum_v)
{
    int count_good = 0;
    r[0] = sum_v;
    for(int i = 1;i <= goodNum;i++)
    {
        if(goods[i].flag == 1)
        {
            r[++count_good] = i;
        }
    }
    return count_good;
}
void findMin(int x)
{
    if(sum_w > maxWeight)
    {
        return;
    }
    //最好在此处判断sun_v是否为最大，这样才不会有sum_w > maxWeight的情况
    if(sum_v > r[0])
    {
        ans = record(sum_v);
    }
    //注意此处循环的条件
    for(int i = x;i < goodNum;i++)
    {
        sum_w += goods[i].weight;
        sum_v += goods[i].value;
        goods[i].flag = 1;
        findMin(i + 1);
        sum_w -= goods[i].weight;
        sum_v -= goods[i].value;
        goods[i].flag = 0;
    }
}

int main()
{
    cin >> goodNum >> maxWeight;
    for(int i = 1;i <= goodNum;i++)
    {
        goods[i].flag = 0;
        cin >> goods[i].weight >> goods[i].value;
    }
    findMin(0);
    for(int i = 1;i <= ans;i++)
    {
        cout << r[i] << " ";
    }
    cout << "maxValue" << r[0] << endl;
    return 0;
}

第一行输入货物总个数和背包的总容量

10 60
23 20
15 14
8 7
20 18
7 5
10 11
9 10
16 15
21 19
13 12

蛮力法：设计算法求解背包问题，并编程实现。

背包问题: 

给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。

背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集。

实验：

编写程序，实现背包问题的蛮力算法。并针对以下两个实例，求出能装到背包中的价值最大的子集。要求输出：最优可行子集和该子集的最大价值。

代码实现：

#include <iostream>

int sum_v;//货物总价值
int sum_w;//货物总重量
int goodNum;//一共有多少货物
int ans;//背包中现有几个货物
int maxWeight;//背包的总容量
int r[100];//记录最后的选择的货物标号

using namespace std;
struct good
{
    int weight;
    int value;
    int flag;//记录该货物是否被挑选
}goods[100];
//更新序列，并返回最大
int record(int sum_v)
{
    int count_good = 0;
    r[0] = sum_v;
    for(int i = 1;i <= goodNum;i++)
    {
        if(goods[i].flag == 1)
        {
            r[++count_good] = i;
        }
    }
    return count_good;
}
void findMin(int x)
{
    if(sum_w > maxWeight)
    {
        return;
    }
    //最好在此处判断sun_v是否为最大，这样才不会有sum_w > maxWeight的情况
    if(sum_v > r[0])
    {
        ans = record(sum_v);
    }
    //注意此处循环的条件
    for(int i = x;i < goodNum;i++)
    {
        sum_w += goods[i].weight;
        sum_v += goods[i].value;
        goods[i].flag = 1;
        findMin(i + 1);
        sum_w -= goods[i].weight;
        sum_v -= goods[i].value;
        goods[i].flag = 0;
    }
}

int main()
{
    cin >> goodNum >> maxWeight;
    for(int i = 1;i <= goodNum;i++)
    {
        goods[i].flag = 0;
        cin >> goods[i].weight >> goods[i].value;
    }
    findMin(0);
    for(int i = 1;i <= ans;i++)
    {
        cout << r[i] << " ";
    }
    cout << "maxValue" << r[0] << endl;
    return 0;
}

第一行输入货物总个数和背包的总容量

10 60
23 20
15 14
8 7
20 18
7 5
10 11
9 10
16 15
21 19
13 12

本文标签： 背包蛮力法