發表新討論
#4726: 可以給提示嗎


popular10347 (ICPC// 哪時能唸到高等演算法T^T)

學校 : 元智大學
編號 : 11351
來源 : [1.169.118.99]
最後登入時間 ：
2012-10-29 00:22:54
b116. TOI2008 3. 加減問題 -- 2008TOI研習營初選 | From: [114.43.63.240] | 發表日期 : 2011-01-10 17:14

這一題解不出來QQ

可以麻煩大大分享一下提示嗎?

 謝謝 !!

 

 
#4728: Re:可以給提示嗎


linishan (L)

學校 : 國立交通大學
編號 : 1090
來源 : [104.132.150.102]
最後登入時間 ：
2019-05-10 19:57:54
b116. TOI2008 3. 加減問題 -- 2008TOI研習營初選 | From: [125.226.10.251] | 發表日期 : 2011-01-10 19:45

這一題解不出來QQ

可以麻煩大大分享一下提示嗎?

 謝謝 !!

 

背包問題 knapsack problem

題目有小小包裝一下 這樣而已 (不懂可以google)

 
#6388: Re:可以給提示嗎


Edgarwu860313 (追隨興國哥)

學校 : 臺南市私立興國高級中學
編號 : 12191
來源 : [219.70.122.78]
最後登入時間 ：
2017-12-30 22:52:20
b116. TOI2008 3. 加減問題 -- 2008TOI研習營初選 | From: [111.242.59.108] | 發表日期 : 2012-02-14 21:07

這一題解不出來QQ

可以麻煩大大分享一下提示嗎?

 謝謝 !!

 

背包問題 knapsack problem

題目有小小包裝一下 這樣而已 (不懂可以google)

 

我想問一下:

        這一題沒有給出正整數的大小,要如何用背包解呢? 


 
#6389: Re:可以給提示嗎


tenyoku8478 (一切都是天意...)

學校 : 高雄市立高雄高級中學
編號 : 13020
來源 : [140.112.16.172]
最後登入時間 ：
2016-03-10 17:17:49
b116. TOI2008 3. 加減問題 -- 2008TOI研習營初選 | From: [218.164.154.192] | 發表日期 : 2012-02-14 21:36

這一題解不出來QQ

可以麻煩大大分享一下提示嗎?

 謝謝 !!

 

背包問題 knapsack problem

題目有小小包裝一下 這樣而已 (不懂可以google)

 

我想問一下:

        這一題沒有給出正整數的大小,要如何用背包解呢? 

1. 可以用STL的vector

2. 動態分配陣列來dp

3. 我猜最大值<100000 開100000的陣列 結果可以過XD(事實上似乎更小)

 

p.s.我也有問題:

請問這題是NP-complete嗎? 還是有不用背包的多項式時間解法? 

 
ZeroJudge Forum