1樓：
題主應該好好看看knapsack這本書。線性01規劃問題已經被研究的非常成熟了。
semidefinite relaxation, lagrangian relaxation效果都不錯啊。但天下沒有免費的午餐，每個具體問題都需要仔細推理驗證，這才是重點。
2樓：花落憶流年
貪婪演算法通常用單位體積的價值來衡量，但是對於不可分割的物體（01揹包）通常得到的不是最優解，可以用分支限界的思路（本質上是一種窮盡的方法，不過在窮盡的過程中加入一些判斷條件能夠大量排出不是最優解的情況）
3樓：Theodore
我覺得這個條件並沒有讓問題更特殊（倒不如說一般的揹包問題，其物品價值和體積都基本都是正相關的）。當遇到一些帶有奇怪條件的看似是DP的問題時，思考的方向無非是增加的條件能不能用來貪心。而這道題明顯是貪不出來的。
4樓：王贇 Maigo
體積和價值正相關是正常的、困難的情況，負相關才是反常的、容易的情況。
所以應該不會有專門針對正相關情況的解法，因為如果有，那麼它就是一般解法……
5樓：Richard Xu
單純從邏輯上分析一下，01揹包實際上是在空間和價值上進行取捨，如果我們希望有乙個不錯的近似解，那麼顯然應該發生在這種空間和價值的衝突不怎麼嚴重的情況下——比如說，如果物體體積和價值負相關，貪心演算法所得到的近似解將會更加接近最優解（似乎就是最優解……）。相反，如果物體體積和價值正相關，那麼這種衝突更加嚴重，反而會使得貪心演算法得不出較好的結果。
6樓：靈劍
自己想的，優先塞單位價值高的，塞滿之後對於剩下的物件判斷能否替代掉一件體積更小的塞進去（總價值一定變大），挑選其中導致已占用體積的平均價值最高的方案，反覆進行直到沒有可行方案為止。
這個按理說肯定有達不到最優解的情況
學歷和個人素質成正相關嗎？
咪咕89757 不是絕對的 個人覺得學歷是素質的一部分，素質包括很多很多方面，就如素質教育，是指全方位發展。學歷可以是篩選素質高低的一種手段，但也就是一種手段，畢竟不可能在可視範圍內分析出乙個人的全部素質，就只能用學歷進行一定的量化。學歷高，品德不好，能力差，等等，那素質依舊很低。相反，學歷低，能力...
肌肉和脂肪含量是成正相關還是負相關？
小熊教練 根據題主的提問，題主可能是剛接觸運動的初學者，個人建議，只關注能量守恆選擇，即，攝入大於消耗，則為增重，肌肉和脂肪都增加。脂肪和肌肉的增加多少，取決於你訓練強度和訓練後的熱量攝入，以及攝入營養素的比例。攝入小於消耗，則為減重，也可以理解為減脂，一般來說，蛋白質作為身體的框架物質，它不會主動...
GPA和科研能力是正相關的嗎？
這個吧，我舉個實際的例子吧。很多人考試sem考了90 但是第一次用，可能連自己的樣品都找不著。所以高的的gpa很多時候並不意味能力，反而可能還會給你一種目空一切的盲目的自信 Prof.鎏 GPA體現的是被動接收知識的能力，科研算是主動解決問題的能力。按道理講不是正相關。但是，一般GPA高的同學，是學...