背包问题：

起初并未想到二进制优化，因为这一题数据范围不大，因此可以用O(n3)的解法，提交代码如下：

 include <bits/stdc++.h>
 using namespace std;
 int n,t;
 int x,w,v;
 int dp[101][1001];
 int main ()
 {
   
   cin>>n>>t;
   
   for(int i=1;i<=n;i++){
     
     cin>>x>>w>>v;
     
   for(int j=1;j<=t;j++){
     
     for(int k=0;k<=x;k++){
       
       if(j>=k*w){
         
         dp[i][j]=max(dp[i][j],dp[i-1][j-k*w]+k*v);
         
         }
       
       }
     
     }
     
   }
   
   cout<<dp[n][t]<<endl;
   
   return 0;
   
 }

后来考虑到如果数据过大，比如是2000或者3000等，上述做法就会超时，因此，我们能想到用二进制优化代码，二进制优化就是本来有n种物品，然后共有count个物品，将它们的相应的个数对应的价值和重量分别存到一个数组中去，最后再写一个二重循环来求解dp数组，dp[i]表示到达i的重量时物品所能达到的最大价值，相应的代码如下：

 include <bits/stdc++.h>
 using namespace std;
 int n,t;
 int x,w,v;
 int v1[1001],w1[1001];
 int dp[1001];
 int main ()
 {
   
   cin>>n>>t;
   
   int count=0;
   
   for(int i=0;i<n;i++){
     
     int k=1;
     
     cin>>x>>w>>v;
     
     while(k<=x){
       
       count++;
       
       w1[count]=k*w;
       
       v1[count]=k*v;
       
       x-=k;
       
       k*=2;
       
       }
     
     if(x){
       
       count++;
       
       w1[count]=x*w;
       
       v1[count]=x*v;
       
     }
     
   }
   
   for(int i=1;i<=count;i++){
     
     for(int j=t;j>=w1[i];j--){
       
       dp[j]=max(dp[j],dp[j-w1[i]]+v1[i]);
       
     }
     
   }
   
   cout<<dp[t]<<endl;
   
   return 0;
   
 }