很经典的01背包， 假设f(i, j)是将i个物品放入容量为j的背包， 那么可得到如下递推式f(i, j) = max(f(i-1, j) , f(i-1, j-c[i])+v[i]))。。。。实现的话有两种方式， 一种是直接用二维数组实现， 另外一种是滚动数组， 不过要注意的是， 如果题意是让这些物品恰好装满背包，那么f(0, 0)为0其他为无穷大， 如果没必要恰好装满那就全部初始化为0；
代码如下：
#include <cstdio> #include <cstring> #include <algorithm>using namespace std; int f[1000 + 10][1000 + 10]; int N, V; int vm[1000 + 10]; //占用的体积 int va[1000 + 10]; //所具有的价值int main() {int T;scanf("%d", &T);while(T--){scanf("%d%d", &N, &V);for(int i=1; i<=N; i++)scanf("%d", &va[i]);for(int i=1; i<=N; i++)scanf("%d", &vm[i]);memset(f, 0, sizeof(f));for(int i=1; i<=N; i++){for(int j=0; j<=V; j++) //前i中物品 容量不超过j时的最大值 不必恰好装满 {if(j >= vm[i]) f[i][j] = max(f[i-1][j], f[i-1][j-vm[i]]+va[i]);else f[i][j] = f[i-1][j];}}printf("%d\n", f[N][V]);}return 0; }
滚动数组
#include <cstdio> #include <algorithm> #include <cstring>using namespace std; int N, V; int vm[1000 + 10]; //体积 int va[1000 + 10]; //价值 int f[1000 + 10]; int main() {int T;scanf("%d", &T);while(T--){scanf("%d%d", &N, &V);for(int i=1; i<=N; i++)scanf("%d", &va[i]);for(int i=1; i<=N; i++)scanf("%d", &vm[i]);memset(f, 0, sizeof(f)); //滚动数组 不是恰好放满的背包for(int i=1; i<=N; i++){for(int j=V; j>=0; j--){if(j-vm[i] >= 0) f[j] = max(f[j], f[j-vm[i]]+va[i]);else f[j] = f[j];}}printf("%d\n", f[V]);}return 0; }
