程序算法求助

Question

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

Answer 1

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)这样理解对不?

Answer 2

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) 

Answer 3

恩 是的  我弄反了应该是先计算B1+...B8 然后判断A1+...A8>=5000?
如果>5000 那么 再算B2+....B9 在判断 B2+....B9 >=5000?
依次判断下去

Answer 4

// 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;
}搞定了.....

Answer 5

1、按A属性递增排序
2、取前8个，得到第一个可能解
3、对可能解进行调整：第I+8个（I=1,2,...）替换到前8个中的第K个。替换原则：A和不超过5000，且B和增大。

Answer 6

<script language='vbs'>class num
dim a1,b1
Public Property let A(num1)
 a1=num1
End PropertyPublic Property get A
 A=a1
End PropertyPublic Property let B(num1)
 b1=num1
End PropertyPublic Property get B
 B=b1
End Propertyend classdim 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 numset arr(5)=new num
set arr(6)=new num
set arr(7)=new num
set arr(8)=new num
set arr(9)=new numset arr(10)=new num
set arr(11)=new num
set arr(12)=new num
arr(0).A=2100
arr(0).B=80arr(1).A=3040
arr(1).B=800arr(2).A=200
arr(2).B=2arr(3).A=316
arr(3).B=18
arr(4).A=449
arr(4).B=78arr(5).A=321
arr(5).B=61arr(6).A=1066
arr(6).B=999arr(7).A=678
arr(7).B=8arr(8).A=49
arr(8).B=1arr(9).A=1238
arr(9).B=181arr(10).A=448
arr(10).B=111arr(11).A=899
arr(11).B=8arr(12).A=232
arr(12).B=45function 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 ifif 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 ifend functionmsgbox knapsack(5000,12, 8)</script>

Answer 7

<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 Propertyend classdim 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
nextfunction 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 ifif 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 ifend functionmsgbox 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的突然觉得自己开窍了一类的事情

Answer 8

与问题的要求有关。是求最优解，还是较佳解。如果是前者，计算所有可能组合的 Sum(A), Sum(B)，抛弃 Sum(A) > 5000 的组合，然后取得 Sum(B) 最大值。

Answer 9

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