--正文

學到了，原來背包還能這么寫

由于最高價值（頂多是五萬）很低而重量（10^8）太大，所以反過來找，f[i]為到達價值i所需的最小空間

? 則 f[i] = min(f[i],f[i-w[i]]+v[i])

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;int f[100000]; int n; int w; int cost[1001],value[1001]; int main(){while (scanf("%d %d",&n,&w) != EOF){int i,j;int maxValue = 0;for (i=1;i<=n;i++){scanf("%d %d",&cost[i],&value[i]);maxValue += value[i];}for (i=1;i<=maxValue;i++){f[i] = w+1;}f[0] = 0;int maxj = 0; for (i=1;i<=n;i++){for (j=maxValue;j>=value[i];j--){f[j] = min(f[j],f[j-value[i]]+cost[i]);}}int maxi = 1;for (i=1;i<=maxValue;i++){if (f[i] > w) continue; maxi = i;}printf("%d\n",maxi);}return 0; }

?

轉載于:https://www.cnblogs.com/ToTOrz/p/6099917.html

總結

以上是生活随笔為你收集整理的XidianOJ 1146 万神的竞赛的全部內容，希望文章能夠幫你解決所遇到的問題。

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