背包问题：爱考，种类多，难度不一
我有一个背包，地下一堆物品，挑选物品放入背包，最大能挑选出来的价值是多少。
牛客DP41 【模板】01背包
1.状态表示
dp[i]:从前i个物品中选，所有选法中，能挑选出来的最大价值（X）
存在问题，我们决定选不选的时候，连基础的背包容量都不清楚，我们并不知道应不应该去选择这个物品,
dp[i]【j】:依旧从前i个物品中选，(总体积不能超过j)所有选法中，能挑选出来的最大价值
(可以使用二维数组的下标，来去表示一些东西，比如体积，位置之类的，不是一定他就是下标)
2.状态转移方程
根据最后一步，分情况讨论
填表顺序：
从上往下选
返回值
dp[n][v]
以上属于第一问的最大价值
第二问最大容量
1.状态表示
dp[i][j]:从前i个物品中挑选，总体积正好等于j,所有选法中，能挑选出来的最大价值，
2.状态转移方程
和上面那个相同
但是有问题，他一定存在这个dp[i-1][j]吗？，假如dp[i][j]=-1;表示没有这种情况。
前i个物品是凑不出来j的
求状态，要判断dp[i][j]是否等于-1;(如果可以让dp[i][j]先等于dp[i-1][j]，假如前一个是-1，那么这一个这种情况本来你就不选i物品，还是没有。
要判断dp[i][j]当选择i物品的时候
w[i]+dp[i-1][j-v[i]],为什么这个情况要去判断，因为这个假如是-1，他还是加上了一个数，导致他有可能会数值出现问题（前i-1个物品中体积恰好为j-v[i]的dp,这个值和w[i]相加就是正确答案）
j-v[i]>=0&&dp[i-1][j-v[i]]!=-1(要在前i-1个物品中正好凑出来j-v[i]的体积，才可以).
3.初始化
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = scanner.nextInt(); int V = scanner.nextInt(); int [][]dp = new int[n + 1][V + 1]; int []w = new int[n]; int []v = new int[n]; for (int i = 0; i < n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } //i表示下标 //j表示背包的体积剩余 for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { if (j - v[i - 1] < 0) { dp[i][j] = dp[i - 1][j]; } else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]); } } System.out.println(dp[n][V]); for (int i = 0; i <= n; i++) { Arrays.fill(dp[i], 0); } for (int i = 1; i <= V; i++) { dp[0][i] = -1; } //dp[i][j]==-1表示没有这种情况 for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; if (j - v[i - 1] >= 0 && dp[i - 1][j - v[i - 1]] != -1) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]); } } } if (dp[n][V] == -1) { System.out.println(0); } else { System.out.println(dp[n][V]); } } }
力扣51.N皇后（可以很好的锻炼代码能力）
这个题的思路，首先
直接暴力初始化，全部为'.',然后我们来暴力搜索可以为Q的情况
我们遍历的时候，要考虑是一个格子一个格子去暴力搜索，还是一行一行去搜素，我们这里选择的是一行一行的去搜索
下面是剪枝策略
下面是剪枝策略
那么有没有一种可能这个b是一个负数呢？换句话说下标可以为负数吗，那么我们该怎么让他变成正的呢？我们设想i-j+n=b+n，此时还是定值，而且i-j肯定是小于n的
class Solution { //小细节，为什么是ArrayList<>(),因为是要标记的char[][]数组， 然后这个char数组，可以转化为List<String> List<List<String>>ret=new ArrayList<>(); boolean checkcol[]; boolean checkdig1[]; boolean checkdig2[]; char [][]path; int n; public List<List<String>> solveNQueens(int n1) { n=n1; path=new char[n][n]; checkcol =new boolean[n]; checkdig1=new boolean[2*n]; checkdig2=new boolean[2*n]; for(int i=0;i<n;i++){ Arrays.fill(path[i],'.'); } dfs(0); return ret; } public void dfs(int row){ if(row==n){ //添加结果 List<String>tmp=new ArrayList<>(); for(int i=0;i<n;i++){ //把字符数组，添加到字符串中 tmp.add(new String(path[i])); } //添加这个String，到List中，然后List<List<String>>去接收 ret.add(new ArrayList<>(tmp)); } for(int col=0;col<n;col++){ if(checkcol[col]==false&&checkdig1[row-col+n]==false&&checkdig2[row+col]==false){ path[row][col]='Q'; checkcol[col]=true; checkdig1[row-col+n]=true; checkdig2[row+col]=true; dfs(row+1); path[row][col]='.'; checkcol[col]=false; checkdig1[row-col+n]=false; checkdig2[row+col]=false; } } } }
