背包问题推广c++.zip

#include<iostream> using namespace std; #define N 5 int C;//背包体积 int W;//背包最大重量 #define max 100 int w[6] = {0, 2 , 3 , 4 , 5 ,7}; //商品的重量 int v[6] = { 0, 3 , 4 , 5 , 6 ,10}; //商品的价值 int c[6] = { 0,1,2,3,4,5, };//商品的体积 int m[max][max][max];//数目，重量，体积 int t[max][max][max]; int x[max]; void knapsack() { int i, j,k; for (j = 1; j <= W; j++) { for (k = 1; k <= C; k++) { if (w[1] <= j && c[1] <= k) { m[1][j][k] = v[1]; t[1][j][k] = 1; } else { m[1][j][k] = 0; t[1][j][k] = 0; } } } for (i = 1; i <= N; i++) for (k = 1; k <= C; k++) m[i][0][k] = 0; for (i = 1; i <= N; i++) for (j = 1; j <= W; j++) m[i][j][0] = 0; for (i = 1; i <=N; i++) { for (j = 1; j <= W; j++) { for (k = 1;k <= C; k++) { if (w[i] <= j && c[i] <= k) { if (m[i - 1][j][k] < m[i - 1][j - w[i]][k - c[i]] + v[i]) { m[i][j][k] = m[i - 1][j - w[i]][k - c[i]] + v[i]; t[i][j][k] = i; } else { m[i][j][k] = m[i - 1][j][k]; t[i][j][k] = t[i - 1][j][k]; } } else { m[i][j][k] = m[i - 1][j][k]; t[i][j][k] = t[i][j][k] = t[i - 1][j][k]; } } } } } void output() { int y = W; int j = N; int f = C; while (y > 0&&f>0) { j = t[j][y][f]; x[j] = 1; y = y - w[j]; f = f - c[j]; } int a; int number = 0;//最大价值 for (int i = 1; i <= N; i++) { a = x[i] * v[i]; number = number + a; } cout << "使用硬币最大价值为：" << number << endl; cout << "硬币的重量：{"; for (int i = 1; i <= N; i++) { cout << w[i] << " "; } cout << "}" << endl; cout << "硬币的价值：{"; for (int i = 1; i <= N; i++) { cout << v[i] << " "; } cout << "}" << endl; cout << "硬币的体积：{"; for (int i = 1; i <= N; i++) { cout << c[i] << " "; } cout << "}" << endl; cout << "最佳装入方案：{"; for (int i = 1; i <= N; i++) { cout << x[i]; if (i != N) { cout << ","; } } cout << "}" << endl; } int main() { cout << "背包体积："; cin >> C; cout << endl; cout << "背包最大承重："; cin >> W; cout << endl; knapsack(); output(); system("pause"); return 0; }