生活随笔
收集整理的這篇文章主要介紹了
2. 01背包问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
01背包問題
先上版子。
#include<iostream>
#include<algorithm>
using namespace std
;
const int maxn
= 1010;
int f
[maxn
][maxn
];
int v
[maxn
],w
[maxn
];
int main()
{int n
,V
;cin
>>n
>>V
;for (int i
=1;i
<=n
;i
++){cin
>>v
[i
]>>w
[i
];}for (int i
=1;i
<=n
;i
++){for (int j
=0;j
<=V
;j
++){if (j
>=v
[i
]) f
[i
][j
] = max(f
[i
-1][j
],f
[i
-1][j
-v
[i
]]+w
[i
]);else f
[i
][j
] = f
[i
-1][j
];}}int Max
= 0;for (int i
=1;i
<=V
;i
++){Max
= max(Max
,f
[n
][i
]);}cout
<<Max
;return 0;
}
板子不懂得推薦看：大佬詳細講解
再來優化：
#include <iostream>
#include <algorithm>
using namespace std
;
const int maxn
= 1010;
int f
[maxn
];
int v
[maxn
], w
[maxn
];
int main()
{int n
, V
;cin
>> n
>> V
;for (int i
= 1; i
<= n
; i
++){cin
>> v
[i
] >> w
[i
];}for (int i
= 1; i
<= n
; i
++){for (int j
= V
; j
>=v
[i
]; j
--){f
[j
] = max(f
[j
], f
[j
- v
[i
]] + w
[i
]);}}cout
<< f
[V
];return 0;
}
總結
以上是生活随笔為你收集整理的2. 01背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
