分治，动态规划，贪心算法的区别与理解

区别与理解

参考

蛮有意思的讲解

分治算法代码

package one_day_mt;
import java.util.Scanner;public class Main {int[] vs = {0,2,4,3,7};//物品的价值int[] ws = {0,2,3,5,5};//背包的重量private int ks(int i,int c) {int result=0;//记录最大价值if(i==0||c==0) {//如果物品序号为0或者背包剩余重量为0return 0;//返回0}else if(ws[i]>c) {//物品的重量大于背包的剩余重量，（装不下）result=ks(i-1,c);}else {//对于装的下的情况，需要考虑装与不装int temp1=ks(i-1,c);//不装int temp2=ks(i-1,c-ws[i])+vs[i];//装result=Math.max(temp1, temp2);//求其中的最大值}return result;}private void test() {int result;result=ks(4,10);System.out.println(result);}public static void main(String[] args){Main m=new Main();m.test();}
}

动态规划

自上而下填表法

package one_day_mt;
import java.util.Scanner;public class Main {int[] vs = {0,2,4,3,7};//物品的价值int[] ws = {0,2,3,5,5};//背包的重量Integer [][]results=new Integer[5][11];private int ks(int i,int c) {int result=0;//记录最大价值if(results[i][c]!=null) {return results[i][c];}if(i==0||c==0) {//如果物品序号为0或者背包剩余重量为0return 0;//返回0}else if(ws[i]>c) {//物品的重量大于背包的剩余重量，（装不下）result=ks(i-1,c);}else {//对于装的下的情况，需要考虑装与不装int temp1=ks(i-1,c);//不装int temp2=ks(i-1,c-ws[i])+vs[i];//装result=Math.max(temp1, temp2);//求其中的最大值results[i][c] = result;}return result;}private void test() {int result;result=ks(4,10);System.out.println(result);}public static void main(String[] args){Main m=new Main();m.test();}
}

自下而上填表法

int[] vs = {0,2,4,3,7};int[] ws = {0,2,3,5,5};Integer[][] results = new Integer[5][11];public void testKnapsack3() {int result = ks3(4,10);System.out.println("最大价值为："+result);System.out.println("二维数组的值为：");for(int i=0;i<5;i++) {for(int j=0;j<11;j++) {System.out.print(results[i][j]+" ");}System.out.println();}}private int ks3(int i, int j){// 初始化for (int m = 0; m <= i; m++){results[m][0] = 0;//当背包剩余重量为0，显然价值为0}for (int m = 0; m <= j; m++){results[0][m] = 0;//当编号重量为0时，显然价值为0}// 开始填表for (int m = 1; m <= i; m++){for (int n = 1; n <= j; n++){if (n < ws[m]){// 装不进去results[m][n] = results[m-1][n];} else {// 容量足够if (results[m-1][n] > results[m-1][n-ws[m]] + vs[m]){// 不装该珠宝，最优价值更大results[m][n] = results[m-1][n];} else {results[m][n] = results[m-1][n-ws[m]] + vs[m];}}}}return results[i][j];}public static void main(String avgs[]) {Main m=new Main();m.testKnapsack3();}
}