1. 问题描述

假如我们有一个背包，在我们面前摆了 i 件物品，这些物品的价值分别为 v,
怎么装可以保证背包里所有物品加起来价值最大。（注意：一件物品只能拿一次）

2. 0/1是什么意思呢？

0代表这个物品不拿，1代表这个物品拿，其实就代表着拿和不拿的问题

3. 分析

有三个物品，它们的重量分别为1，3，2 价值为：1，4，3
现在有个容量为4的背包，怎么装可以保证所装入物品价值总和最大？

物品价值数组: int v[4]={0,1,4,3};
物品重量数组: int w[4]={0,1,3,2};
物品:i 包容量:j其实就是比较 背包的容量 和 物品的重量，分为两种情况：

1. 如果包的容量大于等于物品容量：j>=w[i]
   可以拿，这个时候又分为两种情况，我拿还是不拿，其实就是比较谁的价值大，拿价值大的
   第一种情况：
                    不拿：上一个物品的价值(直接往上看一行 ) dp[i-1][j]。例如：包容量为4，物品为3时，直接看上一行 价值5.
   第二种情况：
                    拿：dp[i-1][j-w[i]]+v[i]。例如：包容量为2，物品为3时，dp[2-1][2-2]+3=3。
2. 如果包容量小于物品重量：j<w[i]
   包装不下物品（不足以放下），相当于不装，不拿的价值就是上一个物品的价值 dp[i][j] = dp[i-1][j]
   例如：包容量为1，商品为2时，就是上一个物品的价值1

状态转移方程：

 dp[i][j] = max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
1

dp[i][j] = max(装它，不装它); 比较看装它还是不装它的价值大

1. 装它
   v[i]: 物品本身的价值
   j-w[i]：包容量减去物品容量
   dp[i-1][j-w[i]]：回到上一行看，剩余背包容量的最大价值
2. 不装它
   dp[i-1][j]：直接往上看一行

4. 代码

#include <iostream>
using namespace std;


int main(){
	int v[4]={0,1,4,3};//物品价值 
	int w[4]={0,1,3,2};//物品重量 
	int dp[10][10] = {0}; //记录状态
	// dp[ i ][ j ]  表示第i件物品，背包容量为 j时的最大价值  
	for(int i=1;i<4;i++){//物品 
		for(int j=1;j<=4;j++){//包容量 
			if(j>=w[i]){//如果包的容量大于等于物品容量 
				dp[i][j] = max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);//状态转移方程 
			}else dp[i][j] = dp[i-1][j];//包容量小于(装不下)物品容量，相当于不装
			cout<<dp[i][j]<<" "; 
		}
		cout<<endl;
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20