好久沒做題了，今天來一發。

根據題意，可以推出狀態轉移方程：

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<iostream> // Required for max #include<cstring> // Required for memset #include<cstdio> // 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<k; z++){int w, u, v;scanf("%d%d%d",&w,&u,&v);s[z].weight = w;s[z].cost = u;s[z].profit = v-u;}// 初始化dp數組memset(dp, 0, sizeof(dp));// 狀態轉移方程 dp[cost][weight] = max(dp[cost][weight], dp[cost-s[i].cost][weight-s[i].weight] + s[i].profit)for(int cost=0; cost<=m; cost++)for(int weight=0; weight<=n; weight++){for(int i=0; i<k; i++){if(cost-s[i].cost>=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 1 1 1 1

示例輸出

0

提示

來源

zmx

轉載于:https://www.cnblogs.com/Genesis2018/p/9079828.html

總結

以上是生活随笔為你收集整理的SDUT OJ[3109] 买买买 背包 dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。