2A+2B+C+D的分解算法问题 ( 积分: 200 )

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-01-24

• #1

有一个问请你帮忙解决，问题是：
可分解项有
(1)A+B+C+D 　　　　　　　　　28元
(2)A+B+C或A+B+D 　　　　　　 23元
(3)B+C+D或A+C+D 　　　　　　 19元
(4)A+B，A+C,A+D,B+C,B+D,C+D 15元
如2A+2B+C+D分解成
一种方法：A+B+C+D、A+B=28元+15元=43元
二种方法：A+B+C、A+B+D=23元+23元=46元
三种方法：A+B、A+B、C+D=45元
四种方法：A+B、A+C、B+D=45元。
当然我先第一种方法更便宜43元最小。
另如2A+2B也要能分解：A+B,A+B=30元
请问有谁能帮我设计这个算法，我给他几百分，另还有给分。急需！！！！

 

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-01-24

• #2

有一个问请你帮忙解决，问题是：
可分解项有
(1)A+B+C+D 　　　　　　　　　28元
(2)A+B+C或A+B+D 　　　　　　 23元
(3)B+C+D或A+C+D 　　　　　　 19元
(4)A+B，A+C,A+D,B+C,B+D,C+D 15元
如2A+2B+C+D分解成
一种方法：A+B+C+D、A+B=28元+15元=43元
二种方法：A+B+C、A+B+D=23元+23元=46元
三种方法：A+B、A+B、C+D=45元
四种方法：A+B、A+C、B+D=45元。
当然我先第一种方法更便宜43元最小。
另如2A+2B也要能分解：A+B,A+B=30元
请问有谁能帮我设计这个算法，我给他几百分，另还有给分。急需！！！！

 

A

arnew

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-01-25

• #3

没看明白什么意思？！
就是求最值的问题，在前面
1、2、3、4的条件下，
2A+2B+C+D的最值是不是呀？

 

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-01-31

• #4

不是求最值，是分解。如2A+2B+C+D是由(1)(2)(3)(4)中的某一个组成的。希望各位能给出一个算法。　

 

W

wwr74

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-01-31

• #5

是不是超市打折计算啊。

 

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-03

• #6

不是，是最优组合算法。也就是找出哪种组合方式最小。

 

金

金卡绣球jk8.com

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-25

• #7

-------------------------------------
他是说：
*个A + *个B + *个C + *个D ；
（*个）可有可无、多个等；
-------------------------------------
先前说的已经省略了......
算法很简单的，一说就会，就看诚意了，

 

M

missinwind

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-03

• #8

看起来是比较简单，但真正实现起来还有难度，得想想。[]

 

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-24

• #9

先把你的算法讲一下，hth0512@tom.com

 

Y

yemu0512

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-24

• #10

好像没有人知道呀！！！

 

W

wwr74

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-24

• #11

有结论别忘了贴上来啊。
这个东西基本是很麻烦的，唉，算法不擅长啊

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-24

• #12

这是一个扩展的背包问题
我给你一个效率不高但比较好理解的算法吧
用递归的方法
共11种元素，用11层的递归来解，每种元素一层
procedure Find
begin
if n>11 then
begin
如果发现比当前最优解更好的解则替换（最优解记录在一个公共变量中）
Exit;
end;
if 当前已经不可能发现更优解 then
Exit;
for i=0 to 最大可能值(这个循环在优化时最好用while来改进)
begin
修改当前的剩余量
find(n+1)
恢复当前的剩余量
end;
end;

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-02-24

• #13

真正优化的时候可以用动态规划来解
这里有很多状态被重复求解了
最苯的优化是用空间换时间
其次是改变运算顺序来优化
建议到www.ioiforum.org或ioi.126.com上去问问
搞信息学竞赛的人对这个太拿手了
（这道题是非常基础的题目）

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-08

• #14

明显的动态规划问题。类似于IOI95的第二题商店购物。题目及解题报告http://oibh.kuye.cn/download/ioi/ioi1995.zip

 

T

thinkflyer

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-08-07

• #15

DP嘛 太明显了
看来这里oier不少啊