6-1-1 Knapsack
分数 8
作者 王灿
单位 浙江大学

Given nn items, where the ii-th one has weight wiw_i and value viv_i. We only have a knapsack with capacity WW which might not be large enough to hold all the items. Fortunately, we can use magic — for item ii, each time the magic can reduce its weight by 11 for the cost of cic_i. On the other hand, the weight of any item must always be positive — meaning that we cannot use magic to reduce the weight to 0 or less. We can use the magic any number of times. The profit of packing item ii into the knapsack is viki×civ_i - k_i\times c_i where kik_i is the number of times we apply the magic on item ii.

The question is: what is the maximum profit we can get?

It is guaranteed that 1n200,1W200,1wi200,1vi106,1ci1061\le n\le 200, 1\le W\le 200,1\le w_{i} \le 200,1\le v_{i} \le 10^6, 1\le c_{i} \le 10^6.

Function Interface:

int knapsack(int n, int W, int w[], int v[], int c[]);

where n represents the number of items. W represents the capacity of the knapsack. The arrays w[0…n-1],v[0…n-1],c[0…n-1] are the weights, values, and costs of the items.

Judge Program:

#include <stdio.h> int knapsack(int n, int W, int w[], int v[], int c[]); const int maxn = 200; int main() { int n, W; int v[maxn], w[maxn], c[maxn]; scanf(“%d %d”, &n, &W); for(int i = 0; i < n; i++) scanf(“%d%d%d”, &w[i], &v[i], &c[i]); printf(“%d\n”, knapsack(n, W, w, v, c)); return 0; } /* Fill your program here*/

Sample Input:

4 10
8 10 2
12 15 3
5 9 2
3 8 1

Sample Output:

17

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C++ (g++)
#define LL long long
LL f[maxn+5][maxn+5];//fi,w
LL _max(LL a, LL b){return a < b? b:a;}
LL myw[maxn],myv[maxn],myc[maxn];
int knapsack(int n, int W, int w[], int v[], int c[]){
// puts("check");
// for(int i =1 ; i <= n;++i) printf("w[%d]=%d",i,w[i]);
// return 0;
LL ans = 0ll;
for(int i = 1; i <= n; ++i){
myw[i]=1ll*w[i-1],myv[i]=1ll*v[i-1],myc[i] = 1ll*c[i-1];
}
for(int i = 1; i <= n; ++i){
for(LL ww = 0; ww <= W; ++ww){
f[i][ww] = _max(f[i-1][ww],f[i][ww-1]);
for(LL realw = 1; realw <= myw[i] &&realw <= ww; ++realw){
LL realv = 1ll*myv[i] - 1ll*(myw[i]-realw)*myc[i];
if(realv <= 0) continue;
f[i][ww] = _max(f[i][ww],f[i-1][ww-realw]+realv);
}
// for(int reserveW = 0; reserveW <= w[i] && reserveW <= ww; ++reserveW){
// // if(1ll*v[i]<= 1ll*(w[i]-reserveW)*c[i]) continue;
// f[i][ww] = _max(f[i][ww],f[i-1][ww-reserveW]+1ll*v[i]-1ll*(w[i]-reserveW)*c[i]);
// }
// printf("f[%d][%d] = %lld\n",i,ww,f[i][ww]);
if(f[i][ww] > ans) ans = f[i][ww];
}
}
return (int)ans;
}
退出答题
Code Completion
当前1 - 1项,共1项
高速下载