动态规划
/*此为动态规划的模板*/
/*模板可粘贴，题解仅供参考*/
#include <bits/stdc++.h>
using namespace std;
int w[10000],c[20000],f[100000];// 物品容量为 w[ ],价值为c[ ],输出为f[ ];
int m,n; // m 为容积，n 为有多少个物品;
int main()
{
cin>>n>>m; // 输入， 注意顺序不要输错;
for(int i=1;i<= n;i++) // 为了下一行的输入;
cin>>w[i] >>c[i]; // 这里依次为物品的 容量 和价值;
// 这里为什么要再进行一次循环？
// 是因为如果连着上一个循环，每进行一次输入就会进行一次运算;
for(int i=1;i<=n;i++) // 这里设f[v]表示不超过 v 公斤的最大价值
for(int v=m;v>=w[i];v–)// 把能够最多承载的价值的值赋给 v
{
// 如果最大容积大于箱子容积，才开始循环
// 如果最大容积小于箱子容积，自然就会跳过;
if(f[v-w[i]]+c[i] >f[v])// 这一步是关键
{
// 判断是否将物品装入箱子内
// 如果目前是最优解，那么下一行就是装入
f[v]=f[v-w[i]]+c[i]; //装入，注意前后顺序不要换
}
}
cout <<f[m];
return 0;
}
/*★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★*/
/*附加典型例题 “采药”代码*/
/*代码一*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int shijian[101],jiazhi[101],a[1001];
int main()
{
int t,m,i,j;
cin>>t>>m;
for(i=1;i<=m;i++)//m为数目
cin>>shijian[i]>>jiazhi[i];
for(i=1;i<=m;i++)
for(j=t;j>=shijian[i];j–)//t为时间
{
a[j]=max(a[j],a[j-shijian[i]]+jiazhi[i]);
}
cout<<a[t]<<endl;
return 0;
}
/*代码二*/
#include <bits/stdc++.h>
using namespace std;
int f[10000],w[1000],c[10000];
int main()
{
int t,m;
cin>>t>>m; // 每种药的摘采时间和价值
for(int i=1;i<=m;i++) // 循环每一种药
cin>>w[i]>>c[i];
for(int i=1;i<=m;i++)
for(int v=t;v>=w[i];v–) //f[v]表示不超过v 的最大价值
if(f[v-w[i]]+c[i]>f[v]) // 同模板相似
f[v]=f[v-w[i]]+c[i];// 判断将草药放入背包是否是更优解
cout<<f[t]; // 输出最优值
}
/*★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★**/
/*由于模板说的比较详细，所以后边的题的讲解不是太准确，见谅*/