c147 - 105北二5搬家規劃問題
題目描述
題目要求在給定物品重量和需求度，以及載重量限制下，計算最多可搬運的總需求度。這是一個典型的 0/1 背包問題變形。
解題思路
本題使用動態規劃解決。ans[j] 表示在載重量為 j 時，可以獲得的最大需求度。我們遍歷每個物品，對於每個物品，我們考慮是否將其放入背包。如果放入，則更新 ans[j + 物品重量] 的值，使其等於 ans[j] + 物品需求度 和原來的 ans[j + 物品重量] 中的最大值。最終，ans 陣列中的最大值即為最多可搬運的總需求度。
複雜度分析
- 時間複雜度: O(n * L)，其中 n 是物品數量，L 是載重量。
- 空間複雜度: O(L)，用於儲存
ans陣列。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define max( x, y ) ( ((x)>(y)) ? (x):(y) )
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int a[100000],it=0,ans[1000001];
int main(){
while(a[it]=read())++it;
int n=(it-1)/2,mx=a[it-1],ac=0;
for(int i=0;i<n;++i)
for(int j=mx-a[i];j>=0;--j)
if(ans[j]||j==0){
int jai=j+a[i];
ans[jai]=max(ans[jai],ans[j]+a[i+n]);
ac=max(ans[jai],ac);
}
write(ac);
}