求思路 怎么判断有没有装满且最大

一、求思路 怎么判断有没有装满且最大

令f(n,w)为从编号为1~n的物品中进行选择，装满容量为w的背包的最大价值：

当w<0时，f(i,w) = -1

当w=0时，f(i,w) = 0

当w>0时，若i<0，则f(i,w) = -1;

否则，令f0 = f(i-1,w)，f1 = (f(i-1,w-wi) >=0 ? f(i-1,w-wi) + vi : -1)，f(i,w) = MAX(f0,f1)。

若f(n,weight)返回-1，则表示没有恰能装满的解，否则其返回值即最优解的价值。

二、01背包问题变种：从给定的N个正数中选取若干个数之和最接近M的JAVA写法

BIAS0:= (C-MA(C,2))/MA(C,2)*100;

BIAS1 := (C-MA(C,12))/MA(C,12)*100;

BIAS2 := (C-MA(C,26))/MA(C,26)*100;

BIAS3 := (C-MA(C,48))/MA(C,48)*100;

HXL:=V/CAPITAL*100;

D1:=INDEXC;

D2:=MA(D1,56);

DR2:=D1/D2<0.94;

E1:=(C-HHV(C,12))/HHV(C,12)*10;

E2:=(C-REF(C,26))/REF(C,26)*10;

三、C++能否解决0-1规划问题的递归解法

背包问题有0-1背包问题和fraction背包问题，前者规定每个物品要么选，要么不选，而fraction knanpsack允许选取一个物品的一部分，0-1背包问题是NP难的，而fraction knapsacks的复杂度是O(n*logn), 只需要将单位物品的价值按降序排列，利用贪心策略选取即可得到最优解。

     给定一个背包，容量为C，有n个物品，重量为n维行向量w，价值为n维行向量v. |v|=|w|=n, n维向量y=[0,1,0….yn]代表物品的选法，其中的没有元素yi，要么是0、要么是1，为零代表选取第i个物品，为0表示不选取第i个物品。 目标函数是:Max(Sum(vi*yi)), 约束条件是sum(wi*yi) <=C, 其中 1=< i <=n.

     背包问题具有最优子结构，令f(n,C)代表，有n个待选物品，背包容量为C时的最优解，此时物品选择向量为y=[y1,y2,…yn], 那么当yn=1时，y’=[y1, y2, …yn-1],必然为f(n-1, C-wn)的物品选择向量，当yn=0时，必然为f(n-1,C)的最优物品选择向量。所以背包问题可以由动态规划来求解。

    根据上面的分析，我们可以得到如下的递归式:

    当wn>C时，  f(n,C)=f(n-1,C);

    当wn<=C时，f(n，C) = max(f(n-1,C), vn+f(n-1, C-wn) );

    初始条件为：f(i, 0) = 0; f(0,i) = 0; f(0,0) = 0;

    根据上面的分析用递归实现的0-1背包代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

#include<iostream>

usingnamespacestd;

constintW = 150;

constintnumber = 5;

constintVALUE[] = {60, 20, 10, 60, 100};

constintWEIGHT[] = {20, 30, 50, 60, 80};

//function Make( i {处理到第i件物品} , j{剩余的空间为j}) :integer;

intMake(inti, intj)

{  

    intr1 = 0;

    intr2 = 0;

    intr = 0;

    if(i == -1)

    {

        return0;

    }

    if(j >= WEIGHT[i])   //背包剩余空间可以放下物品 i  

    {

        r1 = Make(i-1,j - WEIGHT[i]) + VALUE[i]; //第i件物品放入所能得到的价值

        r2 = Make(i-1,j); //第i件物品不放所能得到的价值  

        r = (r1>r2)?r1:r2;

    }   

    returnr;

}

voidmain()

{

    intmaxValue = Make(number-1, W);

    cout<<maxValue: <<maxValue<<endl;

}