有 n 个物体，重量分别为 wi，价值为 vi，在总重量不超过容量 C 的情况下让总价值最高，但不允许只取走部分物体，要拿走只能整个拿走。 n=4,c=2,(v,w)={(1,1),(2,1),(3,1),(4,2)}
思路详解
i\w12111223324435在现有条件下达到目的所有策略中最优的策略。比如f[3][2]=4是如下计算得来 目的： 求当前背包容量为2的最大价值。 策略1：假如3号物品不可选，那么最优的策略是选1和2号物品价值为3 策略2：假如有3号物品可选，那么最优的策略是 V【当前背包容量-3号容量】+V【3号价值】=0+4=4 -------------为何是-3号容量，因为如果逐步尝试。-1，-2都是没有意义的，背包超重了。
对比策略1和2，策略2最优，故f[3][2]=4
public class Main { int n=4; int c=2; int[] v={0,1,2,3,4}; int[] w={0,1,1,1,2}; public void dp(){ int[][] dp=new int[5][3]; for(int i=1;i<=n;i++){ for (int j=1;j<=c;j++){ dp[i][j]=dp[i-1][j]; if (j>=w[i]) { dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } } System.out.println(dp[4][2]); } }思路详解
public class Main { int n=4; int c=2; int[] v={1,2,3,4}; int[] w={1,1,1,2}; static int bestV=0; public void bk(int depth,int preW,int preV) { int curW=preW; int curV=preV; if (depth>=n){ //达到最大深度否 if (bestV<curV) bestV=curV; return; } if (curW+w[depth]<=c){ //满足约束条件否 curW+=w[depth]; curV+=v[depth]; //选取了第i件物品 bk(depth+1,curW,curV); curW-=w[depth]; curV-=v[depth]; } //不选取第i件物品 bk(depth+1,curW,curV); } public static void main(String[] args) { new Main().bk(0, 0, 0); System.out.println(bestV); } }有 n 个物体，重量分别为 wi，价值为 vi，在总重量不超过容量 C 的情况下让总价值最高，允许只取走部分物体。 n=4,c=2,(v,w)={(1,1),(2,1),(3,1),(4,2)}
public class Main { int n=4; int c=2; int[] v={1,2,3,4}; int[] w={1,1,1,2}; public void greed(){ List<kanap>kanapList=new ArrayList<>(); for (int i = 0; i <n ; i++) { kanap kanap = new kanap(); kanap.setI(i); kanap.setPcRatio(v[i]/w[i]); kanapList.add(kanap); } kanapList.sort((kanap x,kanap y)->{return y.getPcRatio()-x.getPcRatio();}); int MaxValue=0; int tempW=0; for (kanap k:kanapList){ tempW+=w[k.getI()]; MaxValue+=v[k.getI()]; if(tempW>c){ MaxValue= MaxValue-v[k.getI()]+(c-(tempW-w[k.getI()]))*k.getPcRatio(); System.out.println(MaxValue); break; } } } class kanap{ Integer i; Integer pcRatio; public Integer getI() { return i; } public void setI(Integer i) { this.i = i; } public Integer getPcRatio() { return pcRatio; } public void setPcRatio(Integer pcRatio) { this.pcRatio = pcRatio; } } }有 n 种物体，重量分别为 wi，价值为 vi，每种物品的数量是无限的 在总重量不超过容量 C 的情况下让总价值最高，但不允许只取走部分物体，要拿走只能整个拿走。 n=4,c=2,(v,w)={(1,1),(2,1),(3,1),(4,2)}
例题： 假设我们有面值为1元、3元和5元的硬币若干枚。怎样用最少的硬币凑够11元？ 【多种解法】
public class CoinCoin { //测试用例 public static void main(String[] args) { int m = 112; int[] temp = coinCoin(m); for(int i = 0; i <= m; i++) { System.out.println(i + "元最少需要" + temp[i] + "个硬币！"); } } //找出最少的钱的数目 private static int[] coinCoin(int m) { int[] a = {1, 3, 5}; //硬币面值 int[] temp = new int[m + 1]; //存储所需硬币的数目 for(int i = 0; i <= m; i++) { temp[i] = i; //默认全部使用1元，则i元最多需要使用i个银币。 } for(int i = 1; i <= m; i++) { //这个外层循坏，依次对1到m个钱数，进行凑数 for(int j = 0; j < 3; j++) { //这个内层循环，每次都会固定执行3次 if(a[j] <= i && temp[i - a[j]] + 1 < temp[i]) { temp[i] = temp[i - a[j]] + 1; } } } return temp; } }有 n 种物体，重量分别为 wi，价值为 vi，物体的数量为ti,在总重量不超过容量 C 的情况下让总价值最高，但不允许只取走部分物体，要拿走只能整个拿走。 n=4,c=2,(v,w,t)={(1,1,1),(2,1,1),(3,1,2),(4,2,2)} 分析及代码实现
例子题目描述 小偷深夜潜入一家珠宝店，店里有5类宝物，体积分别为W{1,3,2,4,5}，对应的价值为V{200,100,300,150,350 }，对应各类宝物的数量分别为N{2,1,3,4,2}。小偷随身只携带了一个容量为5的背包，问小偷应如何选择才能使偷得宝物的价值最大？
public class Main { public static void main(String[] args) { int totalWeight=5;//背包容量 Treasure[] packages={new Treasure(200, 1, 2), new Treasure(100, 3, 1), new Treasure(300, 2, 3), new Treasure(150, 4, 2), new Treasure(350, 5, 2)}; System.out.println(solution1(packages, totalWeight)); } //时间复杂度O(v*Σn[i]) //状态方程f[j]=max{f[j-k*W[i]]+k*v[i]} k∈[0,n[i]] public static int solution1(Treasure[] treasures,int totalVolume) { int maxValue=-1; //参数合法性检查 if(treasures==null||treasures.length==0||totalVolume<0){ maxValue=0; }else { int treasuresClassNum=treasures.length; int[] f=new int[totalVolume+1]; for(int i=0;i<treasuresClassNum;i++){ int currentVolume=treasures[i].getVolume(); int currentValue=treasures[i].getValue(); int currentNum=treasures[i].getNum(); for(int j=totalVolume;j>=currentVolume;j--){ for(int k=0;k<=currentNum&&k*currentVolume<=j;k++){ f[j]=Math.max(f[j], f[j-k*currentVolume]+k*currentValue); } } } maxValue=f[totalVolume]; } return maxValue; } } class Treasure{ private int value;//价值 private int volume;//体积 private int num;//数量 /** * @param value 价值 * @param volume 体积 * @param num 数量 */ public Treasure(int value,int volume,int num) { this.setValue(value); this.setVolume(volume); this.setNum(num); } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getVolume() { return volume; } public void setVolume(int volume) { this.volume = volume; } public int getNum() { return num; } public void setNum(int num) { this.num = num; } }01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件，部分背包是每种只有一件但是可取物体的一部分
01背包，完全背包，多重背包 十大排序算法
