使用C++写一个动态规划中背包问题的模板
时间: 2024-05-05 19:17:38 浏览: 133
C++动态规划源码.zip
好的,下面是使用 C 语言实现动态规划中背包问题的模板:
```
#include <stdio.h>
int max(int a, int b)
{
return a > b ? a : b;
}
int Knapsack(int W, int wt[], int val[], int n)
{
int dp[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (wt[i - 1] <= w) {
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main()
{
int W = 50; // 背包的最大承重
int wt[] = {10, 20, 30}; // 物品的重量
int val[] = {60, 100, 120}; // 物品的价值
int n = sizeof(wt) / sizeof(wt[0]); // 物品的数量
int result = Knapsack(W, wt, val, n);
printf("背包能装下的最大价值为:%d\n", result);
return 0;
}
```
这个模板的实现思路是,建立一个二维的 dp 数组,其中 dp[i][w] 表示前 i 个物品在背包承重为 w 时,能装下的最大价值。当第 i 个物品的重量小于等于背包剩余承重时,有两种选择:选或不选。如果选的话,则能装下的最大价值为第 i 个物品的价值加上前 i - 1 个物品在背包剩余承重为 w - wt[i - 1] 时能装下的最大价值(dp[i - 1][w - wt[i - 1]]);如果不选的话,则能装下的最大价值为前 i - 1 个物品在背包剩余承重为 w 时能装下的最大价值(dp[i - 1][w])。如果第 i 个物品的重量大于背包剩余承重,那么就不能选。最终返回 dp[n][W],即前 n 个物品在背包最大承重为 W 时能装下的最大价值。
阅读全文