背包问题的动态规划解决方案和蛮力解决方案

给定n个重量为w1，w2，...，wn的价值为v1，v2，...，vn的物品和承重量为W的背包，求这些物品中最有价值的一个子集，并且这些物品是不可分割的。

1. 动态规划

这里的思想和上一篇文章基本相同
上一篇
设F(i,j)为能够放进承重量为i的背包中的钱i个物品中最有价值子集的总价值
按照是否包含第i个物品,分为两组，不包含第i个物品，那么F(i,j)=F(i-1,j).
包含第i个物品，F(i,j)=F(i-1,j-w[i])+v[i]。这里还忽略了一种情况如果w[i]>j,也就是说物体i比背包的最大容纳量还要大，那么F(i,j)=F(i-1,j)。
有下面这个公式

(1) F(i,j)=max(F(i-1,j),F(i-1,j-w[i])+v[i])    j>=w[i]
(2) F(i,j)=F(i-1,j)                            j<w[i] 

#include <iostream>
using namespace std;
int maxProfit(int num,int val[],int w[],int n)
{
    int F[num+1][n+1]={0};
    int i,j;
    for(i=1;i<=num;i++)
        for(j=1;j<=n;j++)
        {
            if(j-w[i]>=0)
                F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+val[i]);
            else
                F[i][j]=F[i-1][j];
        }
    return F[num][n];
}
int main()
{
    int num=4;
    int val[num+1]={0,12,10,20,15};
    int w[num+1]={0,2,1,3,2};
    cout<<maxProfit(num,val,w,5);
    return 0;
}

它的时空效率都是O(nW)。

2. 蛮力法
   使用蛮力法首先要求出n个物体的所有子集
   再不断比较找出总质量不大于背包容量的子集中使总价值取最大者。对n个物体有2^{n个子集，所以蛮力法的最低算法复杂度为2}n,也就是说基本是不可行。这里可以利用BRGB来生成子集。生成子集后面的就无关紧要了。今天到此为止，跑步去了！！！