演算法作業三_0-1 Double Knapsack Problem

 avatar
user_3763047219
c_cpp
2 years ago
1.3 kB
1
Indexable
Never
#define _CRT_SCURE_NO_WARNINGS
#include <iostream>

int main() {
	int N = 0, W = 0, V = 0;
	int c[100] = { 0 }, w[100] = { 0 }, v[100] = { 0 };
	int s[100] = { 0 };
	int t_all[100] = { 0 }, pw = 0,pv=0,T=0;
	scanf("%d", &N);
	scanf("%d", &W);
	pw = W;
	scanf("%d", &V);
	pv = V;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &c[i]);
	}
	for (int i = 1; i <= N; i++) {
		scanf("%d", &w[i]);
	}
	for (int i = 1; i <= N; i++) {
		scanf("%d", &v[i]);
	}
	t_all[0] = 0;
	int i = 1;
	int t_index = 1;
	while (pw>0 && pv>0) {
		int q = -1;
		for (int j = i; j <= N; j++) {
			for (int k = j; k <= N; k++) {
				if (w[i] > pw || v[i] > pv) {
				}
				else {
					if (q > c[i] + (pw - w[j]) + (pv - v[k]) + t_all[t_index - 1]) {
						q = q;
					}
					else {
						q = c[i] + (pw - w[j]) + (pv - v[k]) + t_all[t_index - 1];
						if (s[t_index - 1] > i) {
							s[t_index] = s[t_index - 1];
							s[t_index - 1] = i;
						}
						else {
							s[t_index] = i;
						}
					}
				}
			}
		}
		pw = pw - w[i];
		pv = pv - v[i];
		T = T + c[i];
		t_all[t_index] = q;
		i = i + 1;
		t_index = t_index + 1;
	}
	
	printf("%d\n%d\n", T,t_index);
	printf("(%d",s[1]);
	for (int i = 2; i <= t_index; i++) {
		printf(",%d", s[i]);
	}
	printf(")");

}