image.png

1021.货币系统
image.png

523.

image.png

image.png

image.png

性质二使用反证法证明，假设最优解中，bk与a1,a2,…an都不相同，而
a1,a2,…an都可以被b表示，因此bk也可以被b表示，与最优解矛盾。
image.png

性质三也使用反证法证明
image.png

极大线性无关组

先将a1,a2,…an排序。
判断ai是否能被a1~ai-1表示出来。从而决定是否选择ai

image.png

完全背包问题：
image.png

image.png

混合背包问题

image.png

image.png