蛮力法求解0-1背包问题

Question

哪位高手能给一个蛮力法求解0-1背包问题的核心代码

Answer 1

好吧，我的意思是这样的：假设我用数字1,2,3……n来表示物品，而用w[n]来表示第n个物品的重量，v[n]来表示第n个物品的价值，写一个算法来求解背包问题，假设背包最大承重为m。

Answer 2

或者这是我找到的一段代码，就是解决0-1背包问题的，哪位高手能给分析一下这是怎么实现的吗？#include <stdio.h>
#include <math.h>
#include <iostream.h>
#define MAX 100                      // 限定最多物品数void conversion(int n,int b[MAX])
{
int i;
for(i=0;i<MAX;i++)
{
b[i] = n%2;
n = n/2;
if(n==0)break;
}
}void main()
{
int i,j,n,b[MAX],temp[MAX];
float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;
cout<<"输入物品个数:"<<endl;
cin>>n;
for(i=0;i<n;i++)
{
cout<<"请依次输入第"<<i+1<<"个物品的重量和价值"<<endl;
cin>>w[i];
cin>>v[i];
}
cout<<"输入背包的限制重量:";
cin>>tw;
maxv = 0;
/*穷举2n个可能的选择，找出物品的最佳选择*/
for (i=0;i<pow(2,n);i++)
{
       for (j=0;j<n;j++)
       {
              b[j] = 0;
       }
       conversion(i,b);
       temp_v = 0;
       temp_w = 0;
    for (j=0;j<n;j++)
       {
       if (b[j]==1)
       {
                 temp_w = temp_w+w[j];
                 temp_v = temp_v + v[j];
       }
       }
       if ((temp_w < tw)&&(temp_v>maxv))
       {
       for (j=0;j<n;j++)
       {
              temp[j] = 0;
       }
              maxv = temp_v;
for (j=0;j<n;j++)
{
   temp[j] = b[j];
}
       }
}
cout<<"输出放入背包的物品的最大价值:"<<maxv;
cout<<"选择的物品为："<<endl;
for (j=0;j<n;j++)
{
if(temp[j])
cout<<j+1<<"\t";
}
}

Answer 3

你的程序写的很明白，就是穷举。一个物品要么放入背包，要么不放入背包，所有n个物品就可能有2^n个组合，然后它可能就去一个一个去判断每一个组合有没有超过背包的限制，在没有超过的所有组合中查找总价值最大的一个组合。然而这个算法就实在是太土得掉渣了。如果你要的就是这个所谓“蛮力法”，我只能摇摇头。其实如果你什么都选择“最xxx”这种描述方式，就不是追求实用、带有启发规则的程序。实际上如果你写出一个简单的通用启发式规则的程序，最烂的情况下它也就是退化为所谓“蛮力”而已。但是如果你看了这类连个简单启发规则都不考虑的算法，你可能就根本对于改进程序的实用性没有思路了。