每日一题（第34天）：背包问题

1.0-1背包问题

存在N个物品与一个最大承重为W的背包。其中，第i个物品的质量为w[i]，对应的价值为v[i]。目标是确定应将哪些物品放入背包，使得总质量不超过背包的最大承载能力，同时确保所选物品的价值总和达到最大值。该问题的特征在于：每件物品仅有一件，决策时只能选择将其放入或不放入。

设定f[i][j]表示在前i个物品中，使用容量为j的背包所能获得的最大价值。相应的状态转移方程为：f[i][j]=max{f[i-1][j], f[i-1][j-w[i]]+v[i]}，其中v[i]与w[i]分别代表第i件物品的价值与重量。

编写代码时，假设int[] w={2,2,6,5,4};int[] v={6,3,5,4,6};需要注意的是，在计算过程中所求得的最优解是指，在不超过背包容量的前提下所能获得的最大价值。

 import java.util.Iterator;

    
 import java.util.Vector;
    
  
    
 public class bag {//背包
    
 	int maxWeight;
    
 	Vector<thing> things;//存储所选择的物品
    
 	int maxValue;
    
     bag(){this(0);}
    
     bag(int