提示
0-1背包问题不适合用贪心法来求解。以下仅仅是来模拟和解释为什么不能用贪心
问题描述
给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
基本步骤
计算每种物品单位重量的价值vi/wi依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
核心算法
void Knapsack(int n
,float M
,float v
[],float w
[],float x
[])
{
Sort(n
,v
,w
);
int i
;
for (i
=1;i
<=n
;i
++) x
[i
]=0;
float c
=M
;
for (i
=1;i
<=n
;i
++) {
if (w
[i
]>c
) break;
x
[i
]=1;
c
-=w
[i
];
}
if (i
<=n
) x
[i
]=c
/w
[i
];
}
算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。
0-1背包问题不适用贪心算法
背包容量为50kg，物品1, 2和3的容量和价值分别为(10kg, $60), (20kg, $100)和(30kg, $120)。
单位重量价值最高的为物品1，6$/kg。但是依照贪心算法首选物品1却不能获得最优解：
对于0-1背包问题，贪心选择之所以不能得到最优解, 是因为在这种情况下，无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。
由此导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。
