給定n個重量為w1，w2冬三，...匀油，wn的價值為v1，v2勾笆，...敌蚜，vn的物品和承重量為W的背包，求這些物品中最有價值的一個子集窝爪，并且這些物品是不可分割的弛车。
- 動態(tài)規(guī)劃
這里的思想和上一篇文章基本相同
上一篇
設(shè)F(i,j)為能夠放進承重量為i的背包中的錢i個物品中最有價值子集的總價值
按照是否包含第i個物品,分為兩組，不包含第i個物品蒲每，那么F(i,j)=F(i-1,j).
包含第i個物品纷跛，F(xiàn)(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)。
- 蠻力法
使用蠻力法首先要求出n個物體的所有子集
再不斷比較找出總質(zhì)量不大于背包容量的子集中使總價值取最大者。對n個物體有2n個子集叮阅，所以蠻力法的最低算法復(fù)雜度為2n,也就是說基本是不可行刁品。這里可以利用BRGB來生成子集泣特。生成子集后面的就無關(guān)緊要了浩姥。今天到此為止，跑步去了Ｗ茨＠盏！
