今天我再去看完全背包的时候，突然想到，我们能否用贪心算法优化完全背包问题？
思路的来源其实很简单，当背包容量很大的时候，我们一直选择性价比最高的物品应该是没有问题的。当背包容量减小到某个程度的时候，我们再对剩余的背包容量使用DP进行求解，最终把贪心和动态规划两部分的结果加起来即可。
所以现在的关键是确定背包容量减小到什么程度的时候正好合适？
这点我没有证明，也不是很确定，猜测：当背包容量减小到最接近待选的最大物品的重量时即可。
C++代码 + 注释如下：
class Solution {
public:
int backPackIII(vector<int> &cost, vector<int> &value, int m) {
int amount=cost.size(),pos=0,heavy=0,temp=0;
//防止可选物品为0导致下面while无限循环的情况
if(amount==0) return 0;
//获得性价比最高的物品所在的位置
float ratio=0;
for(int i=0;i<amount;i++){
if(ratio<(float)value[i]/cost[i]){
ratio=(float)value[i]/cost[i];
pos=i;
}
}
//获得最重物品的数量
for(auto i:cost) heavy=max(heavy,i);
//贪心，一直选性价比最高的，直到m刚好>=最重物品的重量
while(m>=heavy+cost[pos]){
m-=cost[pos];
temp+=value[pos];
}
//对减小后的m进行动态规划
vector<int> DP(m+1,0);
for(int i=0;i<amount;i++)
for(int j=0;j<=m;j++)
if(j>=cost[i])
DP[j]=max(DP[j],DP[j-cost[i]]+value[i]);
return temp+DP[m];
}
};因为在网上看遍了完全背包的优化方法，但是没有看到使用贪心的，所以我挺怀疑这个思路的正确性，但是又找不到什么反例……如果这个方法有问题，还请大佬们不吝赐教🙏，或者来位大佬证明一波？（明示
ps:如果这个方法真的没问题的话，那么完全背包性能会提升很多：
评论 (1)
暂无评论
