编辑代码

#include <iostream> 
using namespace std;         //01背包问题
int w[1001];  //物品重量
int v[1001];  //物品价值
int m[1001][1001];  //可选 i到n 物品时 的放入背包的最优子结构
 
int main(){   
 int n;   //物品数量
 int c;   //背包容量
 
 cin>>n;
 cin>>c;
 for(int i=1;i<=n;i++){
  cin>>w[i]>>v[i];
 }

 for(int i=0;i<=n;i++){   
  m[i][0]=0;
 }
 for(int j=0;j<=c;j++){
  m[0][j]=0;
 }
 
 for(int i=1;i<=n;i++){
  for(int j=1;j<=c;j++){
   if(j<w[i])      //放不下
       m[i][j]=m[i-1][j];  
   else         //放得下
       m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  //比较 放与不放 的价值
  }
 }
 cout<<m[n][c]<<endl;

}