a587 - 祖靈好孝順 ˋˇˊ
題目描述
題目描述了祖靈在玩遊戲時獲得了許多寶物，每個寶物都有重量和價值。祖靈的背包有重量限制，要求計算祖靈最多可以帶回的寶物總價值。
解題思路
這題是一個典型的 0/1 背包問題。可以使用動態規劃來解決。b[j] 表示背包容量為 j 時，可以獲得的最大價值。對於每個物品，我們考慮是否將其放入背包。如果放入，則背包容量減少物品的重量，價值增加物品的價值。我們比較放入和不放入兩種情況下的最大價值，並選擇較大的值。
程式碼中，a[i][0] 儲存第 i 個物品的重量，a[i][1] 儲存第 i 個物品的價值。b[w+1] 是一個陣列，用於儲存不同背包容量下的最大價值。max 變數用於追蹤目前找到的最大價值。
程式碼使用雙重迴圈來遍歷所有物品和所有可能的背包容量。外層迴圈遍歷物品，內層迴圈遍歷背包容量。對於每個物品和背包容量，程式碼計算將該物品放入背包後的價值，並更新 b 陣列。
複雜度分析
- 時間複雜度: O(N * W)，其中 N 是物品數量，W 是背包的重量限制。
- 空間複雜度: O(W)，其中 W 是背包的重量限制。
程式碼
#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")
#include <stdio.h>
//#define getchar_unlocked getchar
//#define putchar_unlocked putchar
int a[101][2];
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) {
if(x==0){
putchar_unlocked(48);
putchar_unlocked(10);
return;
}
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
putchar_unlocked(10);
}
int main(){
int N,w;
while(N=read()){
for(int i(0);i<N;++i){
a[i][0]=read();
a[i][1]=read();
}
w=read();
int b[w+1]={0},max(0);
for(int i(0);i<N;++i)
for(int j(a[i][0]),jai(0),bjai;j<=w;++j,++jai){
bjai=b[j]+a[i][1];
if(b[jai]<bjai){
b[jai]=bjai;
(max<b[jai])&&(max=b[jai]);
}
}
write(max);
}
}