关于背包 背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

定义 1.我们有n种物品，物品j的重量为wj，价格为pj。 我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。 如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题 。

2.有N件物品和一个容量为V的背包。第i件物品的重量是wi，价值是vi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大，则问题被称为完全背包。

3.有N件物品和一个容量为V的背包。第i件物品的重量是wi，价值是vi，且每个物品最多装ni次。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大，则问题被称 为多重背包。

4.有N件物品和一个容量为V的背包。第i件物品的重量是wi，价值是vi，。每件物品共有三种情况：01，完全，多重。将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大，则问题被称为混合背包。

这些是最基本的背包类型，除此之外，还有分组背包，多维背包，多维多选择背包以及二维背包。

代码 1.01背包 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。 p.s 可以压缩空间，f[v]=max{f[v],f[v-w[i]]+v[i]} （其他自己想hh)

2.完全背包

#include<iostream>
using namespace std;
int findM(int N,int K,int G[],int W[])
{    int *M=new int[N+1],i,j,k;   
      for(i=0;i<N+2;i++)
          M[i]=0;
      for(i=0;i<K;i++)
      {        
          for(j=N;j>=G[i];j--)
               {            
                   for(k=1;j-k*G[i]>=0;k++)
                       {
                          M[j]=M[j]>k*W[i]+M[j-k*G[i]]?M[j]:k*W[i]+M[j-k*G[i]];   
                        }    
               } 
       }  
           return M[N];
}
int main(){
        int N,K,i;
        while(cin>>N>>K)
        {
        int *G=new int[K];        
        int *W=new int[K];        
        for(i=0;i<K;i++)       
        cin>>G[i]>>W[i];        
        cout<<findM(N,K,G,W)<<endl;        
        delete []G;       
        delete []W;    
        }    
     return 0;
}

3.多重背包 和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件……取 n件。令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[v]=max{f[v-kc]+ kw|0<=k<=n}。复杂度是O(V*∑n）。

The end