小明逛超市

題目大意：

有一個大小為n的背包，和m件物品，每件物品都有自己的價格和價值還有個數(shù)，當(dāng)個數(shù)為0時則為無限件，為1實則為1件，求最大的價值

樣例輸入

4 5

5 3 0

5 3 1

4 4 0

2 3 0

3 2 1

樣例輸出

6

【樣例解釋】

買需求度為3的物品兩個，耗費(fèi)22=4元，獲得32=6的需求度

數(shù)據(jù)范圍限制

對于50％的數(shù)據(jù)，1≤m≤20

對于100％的數(shù)據(jù)，1≤m≤100，0≤n≤10000，1≤y≤1000

解題方法：

這道題就是一個混合背包，但他只由完全背包和01背包組成，我就勤奮點(diǎn)把多重背包也打上了比賽是眼瞎，沒看清題，以為有多重背包，但還是AC了，我們不用直接加一重循環(huán)的方法，用二進(jìn)制優(yōu)化，將5分為1，2，2，將8分為1，2，4，1

#include<cstdio> #include<iostream> using namespace std; int n,m,x,y,z,w,t,a[500000],b[500000],f[10000]; int main() {scanf("%d %d",&n,&m);for (int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&z);if (!z) z=n/x;//判斷是否為無限，若為無限則是可以拿的最大個數(shù)t=1;//預(yù)處理while (t<z){a[++w]=x*t;//記錄b[w]=y*t;//記錄z-=t;//剩余個數(shù)減去當(dāng)前個數(shù)t*=2;//當(dāng)前個數(shù)翻倍}if (z)//余下的{a[++w]=x*z;b[w]=y*z;}}for (int i=1;i<=w;i++)for (int j=n;j>=a[i];j--)f[j]=max(f[j-a[i]]+b[i],f[j]);//01背包printf("%d",f[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【背包】小明逛超市（jzoj 2148）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。