看一个样例

【题目描述】 一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,WnW1，W2，...,Wn,它们的价值分别为C1,C2,...,CnC1,C2,...,Cn，求旅行者能获得最大总价值。

【输入】第一行：两个整数，MM(背包容量，M<=200M<=200)和N(物品数量，N<=30N<=30)；第2..N+12..N+1行：每行二个整数Wi，Ci，Wi，Ci，表示每个物品的重量和价值。

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

【输入样例】

2 1
3 3
4 5
7 9
10 4

【输出样例】

12

//用的是二层数组
//1先分析
#include <bits/stdc++.h>
using namespace std;
int n,m,v[250],w[205];//2确定状态变量
int b[2][205]; //4确定边界值这里为0不必额外变换
int main() {
	ios::sync_with_stdio(false);//关闭cin cout输入输出和scanf printf的同步状态
    cin.tie(0);
    cout.tie(0);
	long long n;
	cin>>m>>n;//输入数据
	for(int i=1;i<=n;++i){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=m;++j){
			b[i%2][j]=b[(i+1)%2][j];//如果不变则选上一次的
			if(j>=w[i])b[i%2][j]=max(b[i%2][j],b[(i+1)%2][j-w[i]]+v[i]);//3状态转移方程
		}
	}
	cout<<b[n%2][m];//5 得到答案
	return 0;
}

一共就五步

1. 1.分析是否可以用
2. 2.定义状态变量
3. 3.状态转移方程
4. 4.确定边界值
5. 5.得出答案

回去