背包九讲之01背包

给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

动态规划之二维数组

#include <iostream>
#include <cstring>
using namespace std;
int main(){
  int n,max;  //n,数量；max,最大容量
  cin>>n>>max;

  int dp[n+1][max+1];
  memset(dp,0,sizeof(dp));
  int w[n+1],v[n+1];   //w,weight;v,value
  for(int i=1;i<=n;i++){
    cin>>w[i]>>v[i];
  }

  for(int i =1;i<=n;i++){
    for(int j=1;j<=max;j++){
      if(j<w[i]){
        dp[i][j] = dp[i-1][j];
      }else{
        if(dp[i-1][j] > dp[i-1][j-w[i]]+v[i]){
          dp[i][j] = dp[i-1][j];
        }else{
          dp[i][j] = dp[i-1][j-w[i]]+v[i];
        }
       }   
     }
   }
cout<<dp[n][max]<<endl;
return 0;
}

动态规划之一维数组

#include <iostream>
#include <cstring>
using namespace std;
int main(){
  int n,max;  //n,数量；max,最大容量
  cin>>n>>max;

  int dp[max+1];
  memset(dp,0,sizeof(dp));
  int w[n+1],v[n+1];   //w,weight;v,value
  for(int i=1;i<=n;i++){
    cin>>w[i]>>v[i];
  }

  for(int i =1;i<=n;i++){
    for(int j=max;j>0;j--){
      if(dp[j] < dp[j-w[i]]+v[i] && j-[wi]>=0){
        dp[j] = dp[j-w[i]]+v[i];
       }   
     }
   }
cout<<dp[max]<<endl;
return 0;
}

重点：动态规划的思想，一维数组的倒叙。