Zerojudge

zjc264 神奇的載物任務

連結:https://zerojudge.tw/ShowProblem?problemid=c264
題意:要在大貨車上放貨物，但有重量和力矩限制，問你最大價值為多少

這題顯然是背包問題，重量限制也很常見，可是”力矩”卻是很罕見了。
力矩:為長度乘以重量，所以越重的物體放越前面(長度越短)越好，所以先排序一遍。
而我dp兩個維度為重量和力矩，看在當重量及力矩長度下最大的價值。
原本一開始我是用價值當狀態，紀錄最小的重量和力矩，但是一直WA，後來才明白不能一次變動兩個變數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int N=205;
const int M=2005;
struct Node{
    int w,v;
    bool operator <(const Node&b)const{
        return w>b.w;
    }
};
//#define debug
int main(){
    Node a[N];
    int n,t,L;
    cin>>n>>t>>L;
    for(int i=0;i<n;i++){
        cin>>a[i].w>>a[i].v;
    }
    sort(a,a+n);//越重的越先排
    int dp[N][M]={};//重量weight,力矩torque
    for(int i=0;i<n;i++){
        for(int j=L-1,jj=a[i].w*L;j;j--,jj-=a[i].w){
            if(jj>t)continue;
            for(int k=t-jj;k>=0;k--){
                if(dp[j][k]){
                    dp[j+1][k+jj]=max(dp[j+1][k+jj],dp[j][k]+a[i].v);
                }
            }
        }
        dp[1][a[i].w]=max(dp[1][a[i].w],a[i].v);
    }
    int ans=0;
    for(int i=1;i<=L;i++){
        for(int j=0;j<=t;j++){
            #ifdef debug
                if(dp[i][j])printf("%d %d %d\n",i,j,dp[i][j]);
            #endif // debug
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<'\n';
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts