【c/c++算法刷题笔记】—— 背包问题1_有 n 件物品，第 i 件物品的重量为 （整数）。 对于给定的整数 w， 请选择一些物品，使得拼出

01背包问题

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

笔记

1. 动态规划的两个核心：初始状态和状态转移方程。
2. 01背包问题是指：当物品只有一件时，选择物品放入或不放入背包
3. 根据题意，设数组v[N],w[N]，分别表示每个物品体积和质量；设数组f[N][N]，其中 i 为物品的下标，j 为背包当前的承重（默认背包承重从0到m遍历），f[i][j] 表示当 前 i 个物品可供选则是否放入背包时，在 承重 j 的限制下，背包内物品的最大价值，所以 f[n][m] 为最终结果。核心逻辑：
   
4. 其中，若 j 不能容纳 i ，或能容纳但不放入背包，当前最大价值仍保持 上一次（i-1）时的最大价值；f [i] [j] = f [i-1] [j]；
5. 若 j 能容纳 i 并且放入背包，f [i] [j] = f [i-1] [j-v[i]] + w [i];

/*
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
*/
#include<iostream>
using namespace std;
const int N=1000;
int n,m;
int v[N],w[N]; // 体积  价值 
int f[N][N]; // 前 i 件物品，总体积 j 的 最大价值 
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>v[i]>>w[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){
			f[i][j]=f[i-1][j];
			if(v[i]<=j&&f[i-1][j-v[i]]+w[i]>f[i][j]){
				f[i][j]=f[i-1][j-v[i]]+w[i];
			} 
		}	
	}
	cout<<f[n-1][m]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

最小邮票数

题目描述

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。

笔记

1. 与背包问题对应，n 为 邮票总数，m 为邮票总价值，pri[20] 为 每个邮票面值；num[i][j]保存 邮票张数，其中，i 为邮票下标，j 为当前总价值，f[i][j] 表示 前 i 张邮票可供选择时，在 总价值为 j 的限制下，背包内邮票的最少张数，所以 f[n-1][m] 为最终结果。

2. 数组为全部变量时，存放于堆中；堆中所有数据初始化为0

/*
链接：https://www.nowcoder.com/questionTerminal/83800ae3292b4256b7349ded5f178dd1
来源：牛客网

输入描述:
    有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。


输出描述:
      对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
示例1
输入
10
5
1 3 3 3 4
输出
3
*/

#include <iostream>
#include <algorithm>
using namespace std;
int pri[20]; //邮票面值
int num[20][100]; //邮票数量 i:第i个邮票  j:当前邮票总值
int main(){
    	int m,n;
    	while(cin>>m){
	    	cin>>n;
	    	for(int i=0;i<n;i++)cin>>pri[i];
	    	for(int j=0;j<=m;j++)
	    		if(j==pri[0]) num[0][j]=1;
            	else num[0][j]=99999999;	
				num[0][0]=0;
//		for(int i=0;i<=n;i++){
//	    		for(int j=0;j<=m;j++){
//            		cout<<num[i][j]<<" ";
//			}
//			cout<<endl;
//		}
	   	for(int i=1;i<n;i++){
	    	  	for(int j=1;j<=m;j++){
	    	  		num[i][j]=num[i-1][j];
	        		if(pri[i]<=j&&num[i][j]>num[i-1][j-pri[i]]+1){
	         	 		num[i][j]=num[i-1][j-pri[i]]+1;
	      		}
	      	}
	    	}
//	    	for(int i=0;i<n;i++){
//	    		for(int j=0;j<=m;j++){
//            		cout<<num[i][j]<<" ";
//			}
//			cout<<endl;
//		}
	    	if(num[n-1][m]==99999999)cout<<0<<endl;
  		else cout<<num[n-1][m];
	}
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60