和买的书上的有一点点差别

书仩开的数组大小是N（商品数量）*M（背包大小）

这样直接提交到POJ，会提示内存不足

经过分析本次的数据，只和上一行的数据有关系所以鈈需要保存以前的历史数据。

 int pnotIn=0;//当前商品如果不放入的话价值是多少
 pnotIn=RS1[j];//当前商品不放入的话，价值是上一个商品组合的价值
 int pIn=0;//保存当前商品放叺的话价值是多少
 if(weight[i]<=(j+1)){//当前商品太重的话，就不存在当前商品放入的情况所以此处要判断下
 pIn=price[i]+RS1[j-weight[i]];//此处的计算简单，但是要用心揣摩我自己都被绕混了（如果当前商品被放入，价值=( 当前商品的价值+(总容量-当前商品重量)的容量可以存放的最大价值）

发布了261 篇原创文章 · 获赞 2 · 访问量 2万+