菜药背包问题

解题思路:

//背包0-1的问题,核心把“时间”当成背包容量，

//“价值”当成物品价值，标准 0-1 背包倒序刷表即可。

注意事项:

参考代码:

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

//背包0-1的问题,核心把“时间”当成背包容量，

//“价值”当成物品价值，标准 0-1 背包倒序刷表即可。

int main(){

int T,M;

int dp[1001];

scanf("%d %d",&T,&M);

int time[M],value[M];

for(int i=0;i<M;i++){

scanf("%d %d" ,&time[i],&value[i]);

}

memset(dp, 0, sizeof(dp));

  for (int i = 0; i < M; i++) {

        for (int j = T; j >= time[i]; j--) {

        int temp = dp[j - time[i]] + value[i];

            if (temp > dp[j]) {

                dp[j] = temp;

            }

        }

    }

    printf("%d\n", dp[T]);

    return 0;

}