P1048 [NOIP2005 普及组] 采药

T就是背包的体积，M就是物品的数量，c[i]就是物品的体积，v[i] 就是物品的价值。

AC代码

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

P1060 [NOIP2006 普及组] 开心的金明

这里物品的价值变成了价格与重要度乘积之和，所以需要更新一下

AC代码

#include<bits/stdc++.h>
using namespace std;
int N,M,c[30],v[30],dp[30005];
int  main()
{cin >> N >> M;for(int i=1;i<=M;i++){cin >> c[i] >> v[i];v[i]=c[i]*v[i];}for(int i=1;i<=M;i++)for(int j=N ; j>=c[i];j--)dp[j] = max( dp[j], dp[j-c[i]] + v[i]);cout << dp[N];return 0;
}

P1049 [NOIP2001 普及组] 装箱问题

没有体积，只有价值，此题物品的价值与体积一样

AC代码

#include<bits/stdc++.h>
using namespace std;
int N,M,c[35],v[35],dp[20005];
int  main()
{cin >> M >> N;for(int i=1;i<=N;i++){cin >> c[i];v[i]=c[i];}for(int i=1;i<=N;i++)for(int j=M ; j>=c[i];j--)dp[j] = max( dp[j], dp[j-c[i]] + v[i]);cout << M-dp[M];return 0;
}

P1164 小A点菜

此题同上题一样，物品的价值与体积一样，但此问题问的是有多少种方法？在初始状态下有不选这种方法，所以初始化时初始化为1，在核心代码那里只需累加每次方法即可。

此题和上题都是可以优化的，但我都没有优化，方便记忆模板，后续做此类01背包题都是直接套用模板。

AC代码

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

P1734 最大约数和

这个题一眼看下不像01背包，深入一下，把他给的样例手写一下，就知道这是个01背包了，背包体积为S，背包数量也为S，物品体积就为1至S,物品价值就为这个物品的约数之和。

AC代码

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