1 //二维费用的01背包 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 int n , m , L; 8 const int size = 110; 9 const int inf = 0x3f3f3f3f;10 int dp[size*10][size];11 int cost[size];12 int value[size];13 14 void zeroOne( )15 {16     for( int i = 0 ; i<n ; i++ )17     {18         for( int j = L ; j>=cost[i] ; j-- )19         {20             for( int k = m ; k>=1 ; k-- )21             {22                 dp[j][k] = max( dp[j][k] , dp[ j-cost[i] ][k-1] + value[i] );23             }24         }25     }26 }27 28 int main()29 {30     int t , ans;31     cin >> t;32     while( t-- )33     {34         memset( dp , -inf , sizeof(dp) );35         for( int i = 0 ; i<size ; i++ )36         {37             dp[i][0] = 0;38         }39         cin >> n >> m >> L;40         for( int i = 0 ; i<n ; i++ )41         {42             cin >> cost[i] >> value[i];43         }44         zeroOne();45         ans = 0;46         /*47         for( int i = 0 ; i<=L ; i++ )48         {49             for( int j = 0 ; j<=m ; j++ )50             {51                 cout << dp[i][j] << " ";52             }53             cout << endl;54         }55         */56         cout << max(ans,dp[L][m]) << endl;57     }58     return 0;59 }

 1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #define MAX(a,b) (a>b?a:b) 5 int dp[110][1100]; 6 int main() 7 { 8     int L; //最多看L分钟的动漫 9     int N; //总共有N部电影10     int V[110];//每部电影的价值是Vi11     int T[110];//每部电影所播放的时间， 超过时间不会停止一直到电影结束12     int M; //只能买M部电影13     int t, i, j, k, max;14     scanf("%d",&t);15     while(t--)16     {17         scanf("%d%d%d",&N,&M,&L);18         memset(dp,-1,sizeof(dp));//初始化未-1 很多人不明白我会在下面写19         dp[0][0] = 0;//20         for(i = 1; i<= N; i++)21             scanf("%d%d",&T[i],&V[i]);22         for(i = 1; i<= N; i++)//总共N部电影23         {24             for(j = M; j >= 1; j--)//0-1背包问题 只能选一个 要从大到小25             {26                 for(k = L; k >= T[i]; k--)//0-1背包问题 只能选一个 要从大到小 两个维度都是此思路27                 { 28                     //dp[所选电影的件数][电影的时间长度] = 价值29                     if(dp[j - 1][k - T[i]] != -1)30                     /* 当dp[j - 1][k - T[i]] == -1 时31                     也就是说即使你将这个物品加入进来也是不够j部电影的32                     即前 j - 1部 没有凑够 j-1部电影, 此时你这个情况是不能再处理的33                     */34                         dp[j][k] = MAX(dp[j][k],dp[j - 1][k - T[i]] + V[i]);35                 }36             }37         }38         max = 0;39         /*40         for(  i = 0 ; i<=L ; i++ )41         {42             for(  j = 0 ; j<=M ; j++ )43             {44                 printf("%d  ",dp[j][i]);45             }46             printf("\n");47         }48         */49         for(i = 0; i <= L; i++)50         {51             if(dp[M][i] > max)////dp[所选电影的件数][电影的时间长度] = 价值 根据电影数找出最大的价值52                 max = dp[M][i];53         }54         printf("%d\n",max);55     }56     return 0;57 }/*对你有帮助的话请留名*/