程序算法求助

有一组对象（100个左右）数组，具有两个属性A和B都是单精度数值型，现在希望找出其中的8个，满足条件8个的A的合计数值不超过5000的情况下，B的合计最大。请问大家这个程序如何写？ --------------------编程问答-------------------- 这个蛮考人的，帮顶。 --------------------编程问答-------------------- 穷举~~~ --------------------编程问答-------------------- 飘过 --------------------编程问答--------------------

引用 2 楼 chinayuppie 的回复:

穷举~~~

能具体说说吗 --------------------编程问答-------------------- 1.
假定有100对象,按B排降序
2.
for i=1 to 93
A=A(i+0)+A(i+1)+...+A(i+7)
if rul<=5000 then
exit for
next
B=B(i+0)+B(i+1)+...+B(i+7)

这样理解对不? --------------------编程问答-------------------- for i=1 to 93
    A=A(i+0)+A(i+1)+...+A(i+7)
    if A <=5000 then
        exit for
    next
B=B(i+0)+B(i+1)+...+B(i+7)
--------------------编程问答-------------------- 确实比较考人。

楼上的算法，严格说来，不是正确的答案。
--------------------编程问答--------------------

引用 7 楼 chen8013 的回复:

确实比较考人。

楼上的算法，严格说来，不是正确的答案。

恩是的  我弄反了

应该是先计算B1+...B8 然后判断A1+...A8>=5000?
如果>5000 那么再算B2+....B9 在判断 B2+....B9 >=5000?
依次判断下去 --------------------编程问答-------------------- 典型的0-1背包问题....我随后给程序 --------------------编程问答-------------------- // adox.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#import "c:\Program Files\Common Files\System\ado\msado15.dll" rename("EOF", "EndOfFile")
#import "c:\Program Files\Common Files\System\ado\msadox.dll" no_namespace
#include "iostream"
#include "icrsint.h"
using namespace std;

inline void TESTHR(HRESULT x) { if FAILED(x) _com_issue_error(x); };

int _tmain(int argc, _TCHAR* argv[])
{
if ( FAILED( ::CoInitialize(NULL) ) )
      return -1;
HRESULT hr = S_OK;
_CatalogPtr m_pCatalog = NULL;
     _ColumnPtr m_pColumn = NULL;
     _TablePtr m_pTable = NULL;
_bstr_t strcnn("Provider=Microsoft.ACE.OLEDB.12.0;Data Source= 'c:\\test.accdb';");
// Define ADODB object pointers
ADODB::_ConnectionPtr m_pCnn = NULL;
TESTHR(hr = m_pCnn.CreateInstance(__uuidof (ADODB::Connection)));
     TESTHR(hr = m_pCatalog.CreateInstance(__uuidof (Catalog)));
     TESTHR(hr = m_pColumn.CreateInstance(__uuidof(Column)));

m_pCnn->Open(strcnn, "", "", NULL);
     m_pCatalog->PutActiveConnection(_variant_t((IDispatch *) m_pCnn));
     m_pTable= m_pCatalog->Tables->GetItem("B1");
m_pTable->Name = "T";

if (m_pCnn)
      if (m_pCnn->State == 1)
         m_pCnn->Close();



CoUninitialize();

return 0;
}

搞定了..... --------------------编程问答-------------------- 不好意思答错地方了.... --------------------编程问答-------------------- 友情Up.......................
--------------------编程问答-------------------- 1、按A属性递增排序
2、取前8个，得到第一个可能解
3、对可能解进行调整：第I+8个（I=1,2,...）替换到前8个中的第K个。替换原则：A和不超过5000，且B和增大。 --------------------编程问答-------------------- <script language='vbs'>

class num
dim a1,b1
Public Property let A(num1)
a1=num1
End Property

Public Property get A
A=a1
End Property

Public Property let B(num1)
b1=num1
End Property

Public Property get B
B=b1
End Property

end class

dim arr(12),maxP
maxP=5000
dim c(12,5000)
set arr(0)=new num
set arr(1)=new num
set arr(2)=new num
set arr(3)=new num
set arr(4)=new num

set arr(5)=new num
set arr(6)=new num
set arr(7)=new num
set arr(8)=new num
set arr(9)=new num

set arr(10)=new num
set arr(11)=new num
set arr(12)=new num

arr(0).A=2100
arr(0).B=80

arr(1).A=3040
arr(1).B=800

arr(2).A=200
arr(2).B=2

arr(3).A=316
arr(3).B=18
arr(4).A=449
arr(4).B=78

arr(5).A=321
arr(5).B=61

arr(6).A=1066
arr(6).B=999

arr(7).A=678
arr(7).B=8

arr(8).A=49
arr(8).B=1

arr(9).A=1238
arr(9).B=181

arr(10).A=448
arr(10).B=111

arr(11).A=899
arr(11).B=8

arr(12).A=232
arr(12).B=45

function knapsack(m,n,t)
if t=0 then
Exit Function
end if
if n=0 then
c(0,m)=0
knapsack=0
Exit Function
end if

if arr(n).A<maxP and m>=arr(n).A then
dim s1,s2

if not IsEmpty(c(n-1, m-arr(n).A)) then
document.write(arr(n).A & " " &  arr(n).B & "<br>")
        s1=arr(n).B+c(n-1, m-arr(n).A)
else
c(n-1, m-arr(n).A)=knapsack(m-arr(n).A, n-1, t-1)
s1=arr(n).B+c(n-1, m-arr(n).A)
end if
if not IsEmpty(c(n-1,m)) then
        s2=c(n-1,m)
else
c(n-1,m)=knapsack(m, n-1, t)
s2=c(n-1,m)
end if

if s1>s2 then
knapsack=s1
Exit Function
else
       knapsack=s2
       Exit Function
end if
else
knapsack=knapsack(m,n-1,t)
Exit Function
end if

end function

msgbox knapsack(5000,12, 8)

</script> --------------------编程问答-------------------- 搞定了,0 1背包动态规划的方法,解决了 --------------------编程问答--------------------



<script language='vbs'>



class num

	dim a1,b1

	Public Property let A(num1)

	 a1=num1

	End Property



	Public Property get A

	 A=a1

	End Property



	Public Property let B(num1)

	 b1=num1

	End Property



	Public Property get B

	 B=b1

	End Property



end class



dim arr(99),maxP

maxP=5000

dim c(99,5000)

Randomize 

for i=0 to 99

	set arr(i)=new num

	arr(i).A=rnd*10000

	arr(i).B=rnd*1000

next



function knapsack(m,n,t)

if t=0 then

	Exit Function

end if

if n=0 then

	c(0,m)=0

	knapsack=0

	Exit Function

end if



if arr(n).A<maxP and m>=arr(n).A then

	dim s1,s2

	

	if not IsEmpty(c(n-1, m-arr(n).A)) then

		document.write(arr(n).A & " " &  arr(n).B & "<br>")

	        s1=arr(n).B+c(n-1, m-arr(n).A)		

	else

		c(n-1, m-arr(n).A)=knapsack(m-arr(n).A, n-1, t-1) 

		s1=arr(n).B+c(n-1, m-arr(n).A)

	end if

	if not IsEmpty(c(n-1,m)) then

	        s2=c(n-1,m)

	else

		c(n-1,m)=knapsack(m, n-1, t)

		s2=c(n-1,m)

	end if

	

	

	if s1>s2 then

		knapsack=s1

		Exit Function

	else

	       knapsack=s2

	       Exit Function

	end if

else

	knapsack=knapsack(m,n-1,t)

	Exit Function

end if



end function



msgbox knapsack(5000,99, 4)



</script>

0-1背包解法

f(n,m)=max{f(n-1,m),f(n-1,m-v[n])+p[n]}
其中n代表了第几个物品,m代表了离散的重量 v代表了重量的数组 p代表了权重

关于整体的思路请参考google 0 1背包算法动态规划思想还是很nb的。。。突然觉得自己开窍了

一类的事情 --------------------编程问答--------------------
与问题的要求有关。是求最优解，还是较佳解。

如果是前者，计算所有可能组合的 Sum(A), Sum(B)，抛弃 Sum(A) > 5000 的组合，然后取得 Sum(B) 最大值。
--------------------编程问答--------------------
较佳解的方法就很多了。

例如，将数组先按 B 排序，然后，将 B 相等的多个数组（如果有）去掉 A 较大者，只留最小的一个。然后试算前 8 项的 Sum(A)，如果超过 5000，去除其中 A 最大者重新尝试，直至得到 Sum(A) <= 5000。前 8 项就是一个较佳解。

补充：VB ,  基础类