C++ 0-1背包

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxm=201,maxn=31;
int m,n;
int w[maxn],c[maxn];
int f[maxn][maxm];
int max(int x,int y)
{
    if(x<y)return y;
    else return x;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>c[i];
    for(int i=1;i<=n;i++)
    for(int v=m;v>0;v--)
    if(w[i]<=v)f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
    else f[i][v]=f[i-1][v];
    cout<<f[n][m];
    return 0;
}

先把代码写出来，再做解释了。

背包问题是一种经典的动态规划的试题。

试题描述：

经典的 0-1 背包：知道 n 个物品的体积和价值，第 i 个体积为 V[i]，价值为 W[i]，有一个背包的容积为 C。求在体积不超容积的前提下，背包中可装物品价值的最大值。

输入：

第一行：两个整数 n 和 C ；
第 2 行到第 n+1 行：每行两个整数 Vi 与 Wi，有一个空格分隔。

输出：

一个数，表示背包中能得到物品价值的最大值。

输入示例：

2 10
1 1
2 2

输出示例：

所以根据题目可知这道题还是动态规划（废话）；

重点：

1. 0-1背包，意味着bool类型的正确或错误，在背包问题中就意味着选择装入或者不装入；

2.动态规划的方程式：定义状态f[i,v],表示前i件物品放入一个容量为v的背包可以获得的最大值，所以转移方程为 f[i,v]=max(f[i-1,v],f[i-1,v-c[i]]+w[i]);不要忘了用二维数组；

PS：方案总数为2的N次方（不会打）；

时间复杂度为 O（NV）；

3.经。。。发现f[i,v]是由f[i-1,v-c[i]]和f[i-1,v]两个式子递推而来的（递推没学好的需要补）；可是我们又可以采取什么方法取f[i-1,v-c[i]]和f[i-1,v]的值呢？

这并不容易；但只要你使用主循环v=v~0的递减循序计算；

i也就表示为背包中剩余的容量了！；

（本人很水）；