好久没做题了，今天来一发。

根据题意，可以推出状态转移方程：

dp[cost][weight] = max(dp[cost][weight], dp[cost-s[i].cost][weight-s[i].weight] + s[i].profit)

cost与weight可以互换

毕竟基础差，看了许久，又在舍友的讲解下才明白思路(o´・ェ・｀o)

后来还因为个人细节没注意到，WA了一次......

加注释后的代码如下（尝试着优化，结果效果相差不大  (。・・)ノ  书看得少），题目在文章后面给出

#include
    
        // Required for max#include
     
          // Required for memset#include
      
            // Required fro scanf,printf#define MAX 101      // 题目中最大数为100，所以数组下界为101// 存储货物的重量、进价、盈利struct { int weight, cost, profit;}s[MAX];// dp数组int dp[MAX][MAX];int main(){    int n, m, k;    while(scanf("%d%d%d",&n,&m,&k) != EOF)    {        // 对输入的数据处理后存在结构体中        for(int z=0; z
       
        =0 && weight-s[i].weight>=0)                        dp[cost][weight] = std::max(dp[cost][weight], dp[cost-s[i].cost][weight-s[i].weight] + s[i].profit);                }            }        printf("%d\n", dp[m][n]);    }    return 0;}
       
      
     
    

买买买

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

我飞最近开始跑商了，比如从淄博往黄岛贩烧饼，从黄岛往淄博贩鱿鱼干。

当然我飞壕还会贩别的。

现在已知黄岛有K种商品，每种商品重量为W，在黄岛买价为U，在淄博卖价为V。

由于我飞经常锻炼身体强壮，每次都能扛总重量不超过N的货物，现在我飞身上有钱M，请你帮我飞计算一下他这一次从黄岛到淄博最多能赚多少钱，假设每种商品都有无穷多。所有的商品不可被分割，即若购买必须购买整件商品。

输入

多组数据。

对于每组数据的第一行有三个整数N,M,K(1 <= N,M,K <= 100)。

接下来的K行，每行三个整数W,U,V(1 <= W,U,V <= 100)。

输出

对于每组数据输出一个整数代表我飞的最大收益。

示例输入

1 1 11 1 1

示例输出

0

提示

 

来源

 zmx