01背包问题  动态规划
01背包问题是一个很经典的动态规划问题了,其特点在于对于当前物品选或不选进行判断

接下来看代码:
class Back {
	static int[] V, M;
	static int[][] B;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();// 有多少物品
		int m = sc.nextInt();// 背包容量是多少
		V = new int[n + 1];// 每个物品的重量
		M = new int[n + 1];// 每个物品的价值
		B = new int[n + 1][m + 1];// 当装了n件商品,且剩余容量为m时的最大价值
		for (int i = 1; i <= n; i++) {
			V[i] = sc.nextInt();
			M[i] = sc.nextInt();
		}

		for (int i = 1; i <= n; i++) {// 第i件物品
			for (int j = 1; j <= m; j++) {// 当前背包容量
				if (V[i] > j) {// 如果该物品比剩余容量大
					B[i][j] = B[i - 1][j];// 不拿
				} else {
					// 判断拿还是不拿
					int value = Math.max(B[i - 1][j - V[i]] + M[i], B[i - 1][j]);
					B[i][j] = value;
				}
			}
		}
		System.out.println(B[n][m]);
	}
}

package algorithm;
import java.util.Scanner;

public class _3_10_01背包问题 {
	static int k;
	static int C;
	static int[] v=new int[100];
	static int[] w=new int[100];	
	static int[][] m=new int[100][100];
	
	static void knapsack(){
		for(int i=1;i<=k;i++)
			m[i][0]=0;
		
		for(int i=1;i<=C;i++)
			m[0][i]=0;
		
		for(int i=1;i<=k;i++){
			for(int j=1;j<=C;j++){
				if(j<w[i])
					m[i][j]=m[i-1][j];
				else{
					m[i][j]=Math.max(m[i-1][j],v[i]+m[i-1][j-w[i]]);
				}
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		knapsack();
		
	}

}


 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 100
int n,c;
int w[N],v[N];
int dp[100][1000];

int main(){
	memset(dp,0,sizeof(dp));
	cin >> n >>c;
	int i,j;
	for(i=1; i<=n; i++)
	{
		cin >> w[i] >> v[i];
	}
	for(i=1; i<=n; ++i)
	{
		for(j=1; j<=c; ++j)
		{
			if(j>=w[i])
			   dp[i][j] = max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
			else
			   dp[i][j] = dp[i-1][j];
		}
	}
	cout << dp[n][c];
} 

**
01背包问题 动态规划
**
1.动态规划
什么是动态规划？动态规划就是将一个大问题不断向下拆分成小问题，直到拆分出的小问题可以求出其解，然后将小问题的解不断的向上合并，最终得到大问题的解决方案。

　　

2.01背包问题
一个旅行者有一个最多能装m公斤的背包，现在有n中物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？

　　

3.简单思路
1.01背包问题与背包问题的区别在于，01背包，物品的选择只有两种一种是拿，另一种是不拿，而背包问题在于，物品可以只取一部分。所以01背包问题不能用贪心算法解决。

2.以dp[i][j]表示用i种物品，重量为j表示所取得的价值。

3.对于第i种物品，如果第i种物品重量大于j，就证明第i种物品肯定不能取，这时的dp[i][j]=dp[i-1][j]

4.如果第i种物品重量小于j，那就会出现两种情况，采用i的话，物品价值dp[i][j]=采用前面的i-1种物品，所占用的重量为j-i.getweight,所产生的价值+第i 种物品的价值。如果不采用i，价值为dp[i-1][j]。换成数学表达式就是dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);

5.比如当i=5,j=10时，dp[5][10]就代表了所取得的最大价值。到这里我们就完成了任务的一半，接下为我们要寻找到底哪些物品放入了背包，从前面的表达式我们可以发现，当dp[i][j]=dp[i-1][j-weight]时，这时为i的物品就会放入背包，所以我们从结果，开始往回走，遇到这种情况，就说明有物品放入背包，然后物品数减1，重量减去为i的重量，继续，最后就能求出哪 些物品放入背包了。
例题：
1.题目描述:
有如下5种物品，小明的书包最多只能装下8公斤的物品，小明特别贪心，思考怎么选择使自己书包能装下并且得到的价值最大。
物品1:6公斤　　   价值48元

物品2:1公斤  　　 价值7元

物品3:5公斤  　　 价值40元

物品4:2公斤 　　  价值12元

物品5:1公斤  　　 价值8元
2.解题思路:
其实我们正常思维，一般会想，我要尽量装满8公斤，把最大的价值求出来，可是这样的话，就需要用到递归，递归能解出来，只是算法难度高。但是什么是动态规划，动态规划就是逆着来，我要求装8公斤的物品怎么装使得价值最大。我可以先考虑装0公斤，最大价值，再考虑装1公斤最大价值，考虑装2公斤最大价值，装3公斤最大价值，把前面都记录下来。用另外一个temp[i][j]数组记录下来。i呢表示我现在出现的物品的数量，当i循环到最后一个数量的时候就结束了嘛。自己想象一下，我虽然有5件物品，先只给你一件，你判断能不能装下，能装下，那么你就看你装下这件物品，和不装下这件物品哪个价值高，那么记录下来即可。具体填下下面的表试下，真正会填表就差不多了
      0  1  2  3  4  5   6    7    8
      0  0  0  0  0  0   0    0    0
6 48  0  0  0  0  0  0   48  48   48
1 7   0  7  7  7  7  7   48  55   55
5 40  0  7  7  7  7  40  48  55   55
2 12  0  7  12 19 19 40  48  55   60
1 8   0  8  15 20 27 40  48  56   63 

这个表是怎么来的呢?，举个例子，当我横着一排一排填，因为最开始只掉一件物品，开始掉重量是6的物品，到6的时候就能装下了，所以temp[1][6]=48，另外7,8也只有这一件物品填。所以还是一样的。
接下来掉第二个物品，掉下1这个物品了，1的价值是7，也就是temp[2][1] = 7。后面一直到temp[2][5]都是等于7。 重点重点来了，到了temp[2][6]的时候怎么办呢?我们的当然一看就是，我要选第一件物品，它的价值是48，可是选了第一件物品，背包就满了，就不能装第二件重量为1的物品了，所以temp[2][6] = 48。
我们人可以这样思考，关键就来了，关键就是怎么让计算机也可以这样思考呢，我们就需要用代码。其实仔细想想，我掉第二件物品了，判断如果不能装下，那么temp[2][j] = temp[2][j-1] //记住j表示的是我背包现在最大只能装j这么多，那既然这个物品装不下，那么当然不能装了。如果我当前物品重量小于j，那么我就可以选择是装还是不装呢？只要比较装还是不装哪个价值大就行了。如果不装的话价值这个时候的最大价值是不会变的，因为都不装嘛，也就是，temp[2][j] = temp[2-1][j] 。如果我装的话，关键是这个，还是到刚才的到第二件物品的价值为6的时候考虑，如果我装下重量1这个物品，temp[2][6] = temp[2-1][6 - 这个物品的重量] + 物品的价值  //
其实我   temp[2-1][6-这个物品重量]表示我还没装这个物品之前的价值腾出装这个物品的空间，然后加上这个物品的价值进行比较。关键是之前的每一个状态都用数组给记录下来了。关键代码先看一下，结合代码再理解
for(int i=1;i<6;i++) {
    for(int j=1;j<9;j++) {
        if(w[i]<=j) {
            temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]); //其实就是比较物品选还是不选哪种价值大。
        }else {
            temp[i][j] = temp[i-1][j];//第i件物品不能放
        }
    }
}

3.代码示例

import java.util.Scanner;

public class knapsack {
	static int[] w = new int[6];//每件物品的重量
	static int[] v = new int[6];//每件物品的价值
	public static void solution(){
		
		
		int[][] temp = new int[6][9];//8表示背包最多能放8公斤的重量
		for(int j = 0;j < 9;j++){//初始化每一行
			temp[0][j] = 0;
		}
		for(int i = 1;i < 6;i++){//背包重量为0时，最大价值肯定是0
			temp[i][0] = 0;
		}
		
		for(int i = 1;i < 6;i++){//从第一个物品开始选，记录我选了前面出现的物品，背包重量从1-8的能选上的最大值
			for(int j = 1;j < 9;j++){//当i循环到最后一层5的时候，也就是得到了，我5件物品都选上的时候的最大值
				if(w[i] <= j){//重量比这个状态小，那么就能放。就是放与不放的问题，观察室放重量大还是不放重量大
					temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]);
				}else{
					temp[i][j] = temp[i-1][j];//第i件物品不能放
				}
			}
		}
		for(int i = 0;i < 6;i++){
			for(int j = 0;j < 9;j++){
				System.out.print(temp[i][j] + " ");
			}
			System.out.println();
		}
	}
	public static void main(String[] args) {
		System.out.println("请依次输入重量和价值:");
		Scanner scn = new Scanner(System.in);
		for (int i = 0; i < 6; i++) {
			w[i] = scn.nextInt();//输入重量
			v[i] = scn.nextInt();//输入价值
		}
		solution();
		
		
		
	}
}