資料結構
網路
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+ 瀏覽
廣告