问题：

有N件物品和一个容量为V的背包。第i件物品的价值是c[i]，重量是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

这个问题的特点是：每种物品只有一件，可以选择放或者不放。用f[i][j]表示背包当前容量为j,选择装入1-i个物品时的最大价值

在求最优解的背包问题中，一般有两种不同的问法：1、求小于等于背包容量的最优解，即不一定恰好装满背包;2、要求“恰好装满背包”时的最优解.

1、求小于等于背包容量的最优解，即不一定恰好装满背包;

设f[0..N][0..v]=0

2、要求“恰好装满背包”时的最优解.

则f[0][1..v]=-∞,确保当背包不满时得不到最优解（价值最大）

状态转移方程：

1. f[i][j]=f[i-1][j]         j<w[i-1]
2. f[i][j]=max{f[i-1][j].f[i-1][j-w[i-1]]+c[i-1]}        其它

解释：

1.背包当前容量j小于第i件物品的重量w[i-1]，第i件物品装不下，所有不放第i件物品

2.第i件物品可以放下，进行选择，放或者不放

• 如果不放，则问题转化为“前i-1件物品放入容量为j的背包中”
• 如果放，则问题转化为“前i-1件物品放入剩下的容量为j-w[i-1]的背包中”，此时能获得的最大的价值就是f[i-1][j-w[i-1]]再加上通过放入第i件物品获得的价值c[i-1]

在“其它”情况下，f[i][j]的值就是上述两种情况中的最大值

代码：

1 #include
      
        2 using namespace std; 3 int f[100][100]; 4 int Min=-999999; 5 int package(int n,int v,int w[],int c[])    //n-物品数量，v-背包容量，w[]各个物品的重量，c[]对应物品的价值 6 { 7     if(f[n][v]!=0)                    //已计算过该子问题 8         return f[n][v]; 9     if(n==0||v<=0)      //题型一：价值最大，不要求装满10         return 0;11 12     //if(n==0)    //题型二：背包装满的情况下最大价值，设f[0][0]=0，f[0][1..v]=-∞，即当背包不满时没有最优解13     //{14     //    if(v!=0) return Min;15     //    return 0;16     //}17 18     if(v
       
        b?a:b;            //选择价值最大的解25     }26     return f[n][v];27 }28 29 int main()30 {31     memset(f,0,sizeof(f));    //设置边界条件32     int n,v,w[100],c[100];33     cout<<"input the number of items:";34     cin>>n;35     cout<<"input the volume of items:";36     cin>>v;37     cout<<"input the weight of items:";38     for(int i=0;i
        
         >w[i];40     cout<<"input the value of items:";41     for(int i=0;i
         
          >c[i];43     cout<<"the bigest value is:";44     cout<
          
           <
          
         
        
       
      

结果：

问法一：求小于等于背包容量的最优解，即不一定恰好装满背包;

问法二：要求“恰好装满背包”时的最优解.