动态规划——物品无限的背包问题

物品无限的背包问题。有$n$种物品，每种均有无穷多个。第i种物品的体积为$V_i$，重量为$W_i$。选一些物品装到一个容量为$C$的背包中，使得背包内物品在总体积不超过$C$的前提下重量尽量大。$1≤n≤100$，$1≤V_i ≤C≤10000$，$1≤W_i≤10^6$。

记忆化搜索解法

dp要初始化为无法得到的值，比如说-1，使用memset(dp, -1, sizeof(dp))进行初始化。

int dpBag(int S) {int& ans = dp[S];if(ans >= 0) {return ans;}ans = 0;for(int i = 1; i <= n; i++) {if(S >= volumn[i]) {ans = max(ans, dpBag(S - volumn[i]) + weight[i]);}}return ans;
}

递推法

void solve() {dp[0] = 0;int ans = -INF;for(int i = 1; i <= C; i++) {dp[i] = -INF;}for(int i = 1; i <= C; i++) {for(int j = 1; j <= n; j++) {if(i >= volumn[j]) {dp[i] = max(dp[i], dp[i - volumn[j]] + weight[j]);if(dp[i] > ans) {ans = dp[i];}}}}cout << ans << endl;
}

测试主程序

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int MAX_NUM = 100 + 5;
const int MAX_CAPACITY = 10000 + 5;
const int INF = 100000000;// 物品种类
int n;
// 背包容量
int C;
// 体积
int volumn[MAX_NUM];
// 重量
int weight[MAX_NUM];
// dp[i]表示体积为i时的最大重量
int dp[MAX_CAPACITY];void solve() {dp[0] = 0;int ans = -INF;for(int i = 1; i <= C; i++) {dp[i] = -INF;}for(int i = 1; i <= C; i++) {for(int j = 1; j <= n; j++) {if(i >= volumn[j]) {dp[i] = max(dp[i], dp[i - volumn[j]] + weight[j]);if(dp[i] > ans) {ans = dp[i];}}}}cout << ans << endl;
}int dpBag(int S) {int& ans = dp[S];if(ans >= 0) {return ans;}ans = 0;for(int i = 1; i <= n; i++) {if(S >= volumn[i]) {ans = max(ans, dpBag(S - volumn[i]) + weight[i]);}}return ans;
}int main() {while(cin >> n && n) {cin >> C;for(int i = 1; i <= n; i++) {cin >> volumn[i] >> weight[i];}solve();memset(dp, -1, sizeof(dp));cout << dpBag(C) << endl << endl;}return 0;
}

输出数据

3 5
1 2
2 3
3 2
10
103 7
2 1
3 2
4 3
5
53 5
3 3
4 2
3 2
3
30Process returned 0 (0x0)   execution time : 22.801 s
Press any key to continue.