/*
作者:larryzhong
题目:p1102 采药
*/

#include <iostream>
using namespace std;

const int maxn = 1010, maxv = 5010;
long long c[maxn], w[maxn], f[maxn][maxv];

int main() {
    int V, n;
    cin >> V >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int v = 0; v <= V; v++) {
            if (v >= c[i])
                f[i][v] = max(f[i - 1][v], f[i - 1][v - c[i]] + w[i]);
            else
                f[i][v] = f[i - 1][v];
        }
    cout << f[n][V] << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int w[1005];
int k[1005];
int f[1005]; //一维优化
int main()
{
int n,s;
scanf("%d",&s);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&k[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=s;j>=w[i];j--)
{
f[j]=max(f[j-w[i]]+k[i],f[j]);
}
}
printf("%d",f[s]);
return 0;
}

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long t[110],m[110],f[1010][1010];
int main()
{
int a,n;//a表示总时间，n表示山洞里草药的数目
cin>>a>>n;
for(int i=1;i<=n;i++)
cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
for(int i=1;i<=n;i++)
for(int j=0;j<=a;j++)
{
if(j>=t[i])//如果总时间大于采药所需时间
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
else f[i][j]=f[i-1][j];
//对比不采当前草药能获得的最大价值和采当前草药能获得的最大价值
}
cout<<f[n][a]<<endl;//输出最大价值
return 0;
}

c++ 啦啦啦啦啦啦

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long t[110],m[110],f[1010][1010];
int main()
{
int a,n;//a表示总时间，n表示山洞里草药的数目
cin>>a>>n;
for(int i=1;i<=n;i++)
cin>>t[i]>>m[i];//循环输入每种草药采摘所需的时间和价值
for(int i=1;i<=n;i++)
for(int j=0;j<=a;j++)
{
if(j>=t[i])//如果总时间大于采药所需时间
f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+m[i]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][a]<<endl;
return 0;
}

啦啦啦啦啦啦

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long c[1010],w[1010],f[1010][1010];
int main()
{
int V,n;
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>c[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=V;j++)
{
if(j>=c[i])
f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
cout<<f[n][V]<<endl;
return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long ti[10000],vi[10000],f[10000][10000];
int main()
{
    int v,n;
    cin>>v>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>ti[i]>>vi[i];  
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<=v; j++)
        {   
          f[i][j]=f[i-1][j];
            if(j>=ti[i])
                f[i][j]=max(f[i][j],f[i-1][j-ti[i]]+vi[i]);
           
        }
    cout<<f[n][v]<<endl;
    return 0;
}

本题是0/1背包
我关于0/1背包的讲解：【精讲】DP经典问题——0/1背包问题

#include<cstdio>
using namespace std;
int n,t,w,v,f[1001];
int max(int x,int y){
    if(x>y)return x;
    else return y;
}
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&w,&v);
        for(int j=n;j>=w;j--)
            f[j]=max(f[j],f[j-w]+v);        
    }

    printf("%d",f[n]);
}

简单的01背包问题

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[105],w[105];
int dp[1005]; 
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[m];
    return 0;
}

介是一道标准的01背包辣~
01背包是O(NW)的复杂度
所以是双循环枚举呀
第一层1~n枚举物品
第二层W~w[i]枚举背包容量
tips:w[i]指的是第i个物品的体积呀
第二步要推柿子
没对于每个空间，最大价值有两种决策
放：f[j]
不放:f[j-w[i]]+c[i]
求个最大就好啦
上代码啦：
#include<bits/stdc++.h>
using namespace std;
int W,n;
int w[110],c[110],f[1100];
int main()
{
cin>>W>>n;
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int j=W;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);
cout<<f[W];
}
好简单呢~

\(01\)背包模板。 我第一次发题解，大家多多照顾 。

很显然本题的数据范围是\(n \leq 30\)，完全可以用\(dfs+\)一些剪枝写过去。

但是，如果\(n,V \leq 1000\)，那么就只能\(dp\).

用\(dp[i][j]\)表示用\(j\)的容量选择前\(i\)个物品可以获得的最大价值。

那么，我们需要考虑第\(i\)个物品。

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

前者：不选当前的。

后者：选当前的，背包容量缩小，加上当前的价值。

然而数组下标显然非负，所以要保证\(j \geq v_i\)，否则就只能选择dp[i-1][j]

二维数组的好处是：**不用考虑循环的正反问题。**

显然可以弄成一维（滚动数组），但是没必要，那样还要研究循环的正反，太麻烦。（当然除非真的有内存的压缩需求）

献上本巨佬的代码。

#include<bits/stdc++.h>
using namespace std;

int V,n;
int dp[1001][1001];
int v[1001],w[1001];

inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
    int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x;}

int main(){
    V=read(),n=read();
    for(int i=1;i<=n;i++) v[i]=read(),w[i]=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=V;j++){
        dp[i][j]=dp[i-1][j];
        if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    printf("%d\n",dp[n][V]);
    return 0;
}

f是动态规划数组。
x为时间，y为价值。
二维时由上一层推来，状态转移方程：
f[i,j]:=max(f[i,j],f[i-1,j-x]+y);
而现在改成了一维，状态要倒着放，
否则当前一层前面的状态会影响目前的操作。
状态转移方程：
f[i]:=f[i-x]+y;
这绝对是最简单的动规写法......
Pascal程序：
var n,m,i,j,x,y,max:longint;
f:array[0..1001] of longint;
begin
readln(m,n);
for i:=1 to n do
begin
readln(x,y);
for j:=m downto x do
if f[j-x]+y>f[j] then
f[j]:=f[j-x]+y;
end;
for i:=1 to m do
if f[i]>max then
max:=f[i];
writeln(max);
end.

现在这么流行DP吗？
我特别喜欢写DFS，不过是个编程的人都知道暴力是不可以过的。
所以我加了最优性剪枝（启发式搜索）
详见代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 105 ;
int n,m,ans;
struct Node{
    int a,b;//a代表时间，b代表价值 
    double f;//性价比 
}node[N];
bool cmp(Node p,Node q) {
    return p.f>q.f;//按性价比排序 
}
int f(int t,int v){//估值函数 
    int tot=0;
    for(int i=1;t+i<=n;i++)
        if(v>=node[t+i].a){
            v-=node[t+i].a;
            tot+=node[t+i].b;
        }
        else 
            return (int)(tot+v*node[t+i].f);
    return tot;
}
void dfs(int t,int p,int v){
    ans=max(ans,v);
    if(t>n) return ;
    if(f(t,p)+v>ans) dfs(t+1,p,v);//判断，如果后面的药品达不到ans就不搜索了 
    if(node[t].a<=p) dfs(t+1,p-node[t].a,v+node[t].b);
}
int main(){
    scanf("%d %d",&m,&n);//读入大小和 
    for(int i=1;i<=n;i++){
        scanf("%d %d",&node[i].a,&node[i].b);
        node[i].f=1.0*node[i].b/node[i].a;//计算性价比
    }
    sort(node+1,node+n+1,cmp);//按性价比排序 
    dfs(1,m,0);
    printf("%d\n",ans);
    return 0;
}

//来一份记忆化搜索
#include <cstdio>
#include <cstring>
#include <algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define N 1005
using namespace std;

int n,m,f[N][N],val[N],w[N];
int dfs(int i,int v){
    if (f[i][v]!=-1) return f[i][v];
    if (i==0 || v<=0) return 0;
    if (w[i]>v) f[i][v]=dfs(i-1,v);
    else f[i][v]=max(dfs(i-1,v),dfs(i-1,v-w[i])+val[i]);
    return f[i][v];
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&m,&n);
    For(i,1,n){
        scanf("%d%d",&w[i],&val[i]);
    }
    printf("%d\n",dfs(n,m));
    return 0;
}

#include<iostream>
using namespace std;
typedef long long ll;
const int maxx=6666;
int main()
{
ll f[maxx],w[maxx],v[maxx],n,t;
cin>>t>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
for(int j=t;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
cout<<f[t];
return 0;
}

水题，pascal代码见下

program noname01;
var t,m:integer;
  c:array[1..100] of integer;
  w:array[1..100] of integer;
  f:array[1..1000] of integer;
  i,ans:integer;
 procedure zo(cost:integer;weight:integer);
 var v:integer;
 begin
   for v:=t downto cost do
   if f[v-cost]+weight>f[v] then f[v]:=f[v-cost]+weight;
 end;
 begin
 for i:=1 to 1000 do f[i]:=0;
 ans:=0;
  read(t,m);
 for i:=1 to m do
   read(c[i],w[i]);
 for i:= 1 to m do
   zo(c[i],w[i]);
 for i:=1 to t do
   if f[i]>ans then ans:=f[i];
 write(ans);
 end.

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int dp[1000][1000],t[1000],v[1000];
int main(){
    int time_max,item_max,item,time=0;
    memset(dp,0,sizeof(dp));
    memset(t,0,sizeof(t));
    memset(v,0,sizeof(v)); 
    cin>>time_max>>item_max;
    for(item=1;item<=item_max;item++)
        cin>>t[item]>>v[item];
    for(item=1;item<=item_max;item++){
        for(time=time_max;time>=t[item];time--)
            dp[item][time]=max(dp[item-1][time-t[item]]+v[item],dp[item-1][time]);
        for(time=t[item]-1;time>=0;time--)
            dp[item][time]=dp[item-1][time];
    }
    cout<<dp[item_max][time_max]<<endl;
}

典型的01背包问题，用一维数组解决，不需要存数据

import java.util.Scanner;

public class Main {
static Scanner in = new Scanner(System.in);
static int n, m;
static int[] dp = new int[105];
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= m; i++) {
int a = in.nextInt();
int b= in.nextInt();
for (int j = n; j >= 0; j--) {
if (j >= a) {
dp[j] = Math.max(dp[j], dp[j - a] + b);
}
}
}
System.out.println(dp[n]);
}

}

#include<cstdio>
#include<iostream>
int dp[1010];
int w[110], val[110];
int main(){
    int t, m;
    scanf("%d%d", &t, &m);
    for(int i=1; i<=m; i++) scanf("%d%d", &w[i], &val[i]);
    for(int i=1; i<=m; i++)
        for(int j=t; j>=0; j--)
            if(j>=w[i]) dp[j]=std::max(dp[j-w[i]]+val[i], dp[j]);
    printf("%d", dp[t]);
    return 0;
}

第一道DP题，开心(=￣ω￣=)

#include<iostream>
using namespace std;
int h[110],w[110],dp[110][110];
int main()
{
    int t,m;
    cin>>t>>m;
    for(int i=1;i<=m;++i)
    cin>>h[i]>>w[i];
    for(int i=1;i<=m;++i)
    {
        for(int j=t;j>=0;j--)
        {
            if(j>=h[i])
            dp[i][j]=max(dp[i-1][j-h[i]]+w[i],dp[i-1][j]);
            else
            dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[m][t];
    return 0;
}

题目传送门

这是一道裸的01背包，不懂01背包的同学建议大家可以看一下教程

~~如果是已经学会的大佬请跳过~~

给定n种物品，每种物品都有重量wi和价值vi，每种物品只有一个。另外，背包容量为W。求解在不超过背包容量的情况下将哪些物品放入背包，才可以使背包中的物品价值之和最大。每种物品只有一个，要么不放入（0），要么放入（1），因此称之为01背包。
假设第i阶段表示处理第i种物品，第i-1阶段处理第i-1种物品，则当处理第i种物品时，前i-1中物品已经处理完毕，只需考虑第i-1阶段向第i阶段的转移。
状态表示：c[i][j]表示将前i种物品放入容量为j的背包中获得的最大价值。
第i种物品的处理状态包括以下两种
（1）不放入：放入背包的价值不增加，问题转化为“将前i-1种物品放入容量为j的背包中获得的最大价值”，最大价值为c[i-1][j]
（2）放入：在第i种物品放入之前为第i-1阶段，相当于从第i-1阶段向第i阶段转化。问题转化为“将前i-1种物品放入容量为j-w[i]的背包中获得的最大价值”，此时获得最大价值就是c[i-1][j-w[i]],再加上放入第i种物品获得的价值v[i]，总价值为c[i-1][j-w[i]]+v[i]
注意：若背包容量不足，则肯定不可以放入，所以仍为前i-1种的物品处理后的结果：若背包容量充足，则考察在放入、不放入哪种情况下获得的最大价值更大。

状态转移方程：
if (j < w[i])
c[i][j] = c[i-1][j];

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

算法步骤

1）初始化

c[0][j]=0,c[i][0]=0,其中i=0,1,2,…,n,j=0,1,2,…,W，表示第0种物品或背包容量为0时获得的价值为0；

2）循环阶段

(1) 按照状态转移方程处理第1种物品，得到c[1][j],j=1,2,…, W
(2)按照状态转移方程处理第2种物品，得到c[2][j], j=1,2,…, W.
(3)依次类推，得到c[n][j],j=1,2,…w.

3)构造最优解

c[n][W]就是不超过背包容量时可以放入物品的最大价值（最优值）。若还想知道具体放入了哪些物品，则根据c[][]数组逆向构造最优解。对此可以用一维数组x[]来存储解向量，x[i]=1表示第i种物品被放入背包，x[i]=0表示第i种物品未被放入背包。

(1)初始时i=n,j=W。

(2)若c[i][j]>c[i-1][j],则说明第i种物品被放入背包，令x[i]=1,j-=w[i];若c[i][j]<=c[i-1][j],则说明第i种物品没被放入背包，令x[i]=0。

(3)i--,转向第2步，直到 i=1时处理完毕。
此时已经得到解向量（x[1],x[2],…,x[n]），直接输出该解向量，也可以仅把x[i]=1的物品序号i输出。

算法代码：

推理过程请看图解：

回归正题，二维dp代码如下：
cpp
//Lucas Ray
#include <bits/stdc++.h>
#define long long int
using namespace std;
const int maxn = 110;
int t, m, ans = 0;
int v[maxn], w[maxn], dp[maxn][maxn*10]; //v代表时间（即花费），w代表价值
int main() {
scanf ("%d%d", &t, &m);
for (int i = 1; i <= m; i++) {
scanf ("%d%d", &v[i], &w[i]);
}
for (int i = 1; i <= m; i++) {
for (int j = t; j >= 0; j--) {
if (j >= v[i]) {
dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
printf ("%d", dp[m][t]);
return 0;
}


二维dp AC记录

有的大佬看到这里就会说了：你这么菜啊，连一维优化都不会啊

算法优化！！！

状态表示：dp[j]表示将物品放入容量为j的背包中可以获得的最大价值。

那就来看一维优化的代码吧

//Lucas Ray
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 3;
int dp[maxn];
int n, m;
int times[maxn], val[maxn];
inline int read() { //快读
    char a;
    int c=0,y=1;
    a=getchar();
    while(a<'0'||a>'9')
    {
        if(a=='-')
        {
            y=-1;
        }
        a=getchar();
    }
    while(a>='0'&&a<='9')
    {
        c=c*10+a-'0';
        a=getchar();
    }
    return c*y;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        times[i] = read(), val[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= 0; j--) {
            if (j >= times[i])
            dp[j] = max (dp[j], dp[j-times[i]] + val[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

这是蒟蒻发的第一篇题解，制作不易，不喜喷轻点