第一招：动态规划算法
动态规划思想：把问题分解为多个阶段，每个阶段执行决策，记录每一个阶段可达的状态集合（去重后），
基于当前阶段的状态集合，通过决策，推导下一个阶段的状态结婚，动态的往前推进
经典背包问题：有一组不同重量不可分割的物品，需要选择一些装入背包，在满足背包最大重量限制的前提下
，背包中物品的最大重量是多少？
1、把问题分为多个阶段，物品是一个一个装入选择是否装入背包中，每一个物品选择是否装入背包作为一个阶段，共有物品个数个阶段
2、每个阶段做出决策，选择是否装入该物品
3、每个阶段做出决策前有一个当前状态集合，做出决策后也记录可达状态集合（去重）
依次步骤动态的往前推进 阶段就是for循环 决策就是for循环里的逻辑 初始化状态集合，并在执行决策后记录可达的状态集合
循环执行完后，即动态推进结束
public class Packet { public int packet(int[] weights, int maximum) { int number = weights.length; boolean[][] states = new boolean[number][maximum+1];//true表示可达状态 states[0][0] = true; if(weights[0] <= maximum) { states[0][weights[0]] = true; } for(int i=1; i<number; i++) { //装进背包 for(int j=0; j<=maximum; j++) { if(states[i-1][j] && j + weights[i] <= maximum) { states[i][j + weights[i]] = true; } } //不装进背包 for(int j=0; j<=maximum; j++) { if(states[i-1][j]) { states[i][j] = true; } } } for(int i=maximum; i>=0; i--) { if(states[number-1][i]) { return i; } } return 0; } public static void main(String[] args) { Packet demo = new Packet(); int[] weight = {2, 2, 4, 6, 3}; // 物品重量 int n = 5; // 物品个数 int w = 9; // 背包承受的最大重量 System.out.println(demo.packet(weight, w)); } }
第二招：贪心算法
贪心算法思想：每次都选择堆期望值贡献最大的数据
经典背包问题：有一组不同重量不可分割的物品，每个物品都有对象的价值，需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品的最大价值是多少？
public class Packet { public int packet(int[] weights, int[] values, int maximum) { //构建性价比数组 int number = weights.length; double[] w_v = new double[number]; int[] index = new int[number]; for(int i=0; i<number; i++) { w_v[i] = values[i] / weights[i]; index[i] = i; } double temp = 0; int x = -1; for(int i=0; i<number-1; i++) { for(int j=i+1; j<number; j++) { if(w_v[index[j]] > w_v[index[i]]) { temp = w_v[index[j]]; w_v[index[j]] = w_v[index[i]]; w_v[index[i]] = temp; x = index[i]; index[i] = index[j]; index[j] = x; } } } //将排好序的重量和价值分别存到数组中 int[] w1 = new int[number]; int[] v1 = new int[number]; for(int i=0; i<number; i++) { w1[i] = weights[index[i]]; v1[i] = values[index[i]]; } int maxValue = 0; int sumWeight = 0; for(int i=0; i<number; i++) { if(sumWeight + w1[i] <= maximum) {//表示当前物品装得下 sumWeight += w1[i]; maxValue += v1[i]; } } return maxValue; } public static void main(String[] args) { Packet demo = new Packet(); int[] weights = {35, 30, 60, 50, 40, 10, 25}; // 物品重量 int[] values = {10, 40, 30, 50, 35, 40, 30};// 物品价值 int maximum = 150; // 背包承受的最大重量 System.out.println(demo.packet(weights, values, maximum)); } }
原文：https://www.cnblogs.com/jiangwangxiang/p/12764567.html