【0-1背包问题】动态规划算法怎么解决小数输入问题

w2013211609

2017/5/12镜像同步14 回复

因为数组索引的需要，要求所给物品重量为整数。怎么解决这个问题呢？C语言，不用python 如果有现成的C语言代码，求解答

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

chenxiansf机器人#1 · 2017/5/12

01背包和重量是不是小数没关系吧，和容量有关系

w2013211609机器人#2 · 2017/5/13

【在 chenxiansf 的大作中提到: 】 : 01背包和重量是不是小数没关系吧，和容量有关系是想说现在想设置物品的价值可以为小数，物品重量和背包重量都可以是小数。但是，用动态规划不是得用到数组吗，所以就没办法。

chenxiansf机器人#3 · 2017/5/13

哈哈，不知道了。你查查背包九讲里面有没有【在 w2013211609 (9薄荷9) 的大作中提到: 】 : 是想说现在想设置物品的价值可以为小数，物品重量和背包重量都可以是小数。但是，用动态规划不是得用到数组吗，所以就没办法。

a940100079机器人#4 · 2017/5/13

用字典，键值对感觉可以解决吧

Agosits机器人#5 · 2017/5/13

离散一下？

w2013211609机器人#6 · 2017/5/14

【在 a940100079 的大作中提到: 】 : 用字典，键值对感觉可以解决吧？？能具体说下嘛

a940100079机器人#7 · 2017/5/14

假设weight中有01.，0.2，0.8，0.11，0.134，0，34 就把所有weight都×1000，也就是找到最低位的数字，展成整数，然后再用01规划吧（感觉和楼上的离散也是要表达这个意思把）如果用dict的话也是找到最低位的数字，只不过在DP的时候，weight的变化是0.001，而不是整数规划中的1 不知道这么说楼主可以听懂不

w2013211609机器人#8 · 2017/5/15

【在 a940100079 的大作中提到: 】 : 假设weight中有01.，0.2，0.8，0.11，0.134，0，34 : 就把所有weight都×1000，也就是找到最低位的数字，展成整数，然后再用01规划吧（感觉和楼上的离散也是要表达这个意思把） : 如果用dict的话也是找到最低位的数字，只不过在DP的时候，weight的变化是0.001，而不是整数规划中的1 : ................... 哦哦，get it ,谢谢同学，棒

a940100079机器人#9 · 2017/5/15

谢谢夸奖【在 w2013211609 的大作中提到: 】 : 哦哦，get it ,谢谢同学，棒