C++完全背包

【题目描述】

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，
今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。

【输入】

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

【输出】
仅一行，一个数，表示最大总价值。

【输入样例】
10 4
2 1
3 3
4 5
7 9

【输出样例】
max=12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

完全背包：可装物品数量最小为0个，最大就是将背包装满 也就是j/w[i]。

#include <iostream>
using namespace std;

int w[35],c[35],dp[205];
int main(){
	int m,n;//m背包容量，n物品数量 
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];//Wi：物品的重量  Ci：物品的价值 
	}
	for(int i=1;i<=n;i++){//物品
		for(int j=m;j>=1;j--){//逆向推，用到上一条的旧数据
			for(int k=0;k<=j/w[i];k++){//背包容量为j时，可以拿第i个物品的最多个数
				dp[j] = max(dp[j],dp[j-k*w[i]]+k*c[i]);
			} 				
		}
	}
	cout<<"max="<<dp[m];
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 解法二

#include <iostream>
using namespace std;

int w[35],c[35],dp[205];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
//		for(int j=0;j<=m;j++){
//			if(j>=w[i]){
//				dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
//			} 				
//		}
		for(int j=w[i];j<=m;j++){
			dp[j] = max(dp[j],dp[j-w[i]]+c[i]);						
		}
	}
	cout<<"max="<<dp[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