数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法律使用动态规划解决背包问题的 C++ 程序
这是一个使用动态规划解决 0-1 背包问题的 C++ 程序。在 0-1 背包问题中，给定一组物品，每种物品都具有重量和价值。我们需要确定每件物品包含在集合中的数量，以便总重量小于或等于给定的限制，并且总价值尽可能大。
算法
Begin Input set of items each with a weight and a value Set knapsack capacity Create a function that returns maximum of two integers. Create a function which returns the maximum value that can be put in a knapsack of capacity W int knapSack(int W, int w[], int v[], int n) int i, wt; int K[n + 1][W + 1] for i = 0 to n for wt = 0 to W if (i == 0 or wt == 0) Do K[i][wt] = 0 else if (w[i - 1] <= wt) Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i -1][wt]) else K[i][wt] = K[i - 1][wt] return K[n][W] Call the function and print. End
示例代码
#include <iostream>
using namespace std;
int max(int x, int y) {
return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n) {
int i, wt;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (wt = 0; wt <= W; wt++) {
if (i == 0 || wt == 0)
K[i][wt] = 0;
else if (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
else
K[i][wt] = K[i - 1][wt];
}
}
return K[n][W];
}
int main() {
cout << "Enter the number of items in a Knapsack:";
int n, W;
cin >> n;
int v[n], w[n];
for (int i = 0; i < n; i++) {
cout << "Enter value and weight for item " << i << ":";
cin >> v[i];
cin >> w[i];
}
cout << "Enter the capacity of knapsack";
cin >> W;
cout << knapSack(W, w, v, n);
return 0;
}输出
Enter the number of items in a Knapsack:4 Enter value and weight for item 0:10 50 Enter value and weight for item 1:20 60 Enter value and weight for item 2:30 70 Enter value and weight for item 3:40 90 Enter the capacity of knapsack100 40
更新于: 2019-07-30
14K+ 浏览
广告