Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
输入
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
输出
One integer per line representing the maximum of the total value (this number will be less than 231).
示例输入
1
5 10
1 2 3 4 5
5 4 3 2 1
示例输出
14
1 #include<stdio.h>
2 #include<
string.h>
3 int c[
1100][
1100],p[
1100],w[
1100];
//c[i][j]表示前i件物品恰好放入容积为j的背包获得的价值 4 int knaspack(
int m,
int n)
5 {
6 int i, j;
7 memset(c,
0,
sizeof(c));
8 for(i =
1; i < m+
1; i++
)
9 for(j =
1; j< n+
1; j++
)
10 {
//如果第i件物品的体积小于容积j时，可包含两种情况：（1）物品i放入背包，前i-1件物品的体积为j-w[i],所以c[i][j]=c[i-1][j-w[i]]+p[i]; (2)物品i不放入背包中，则c[i][j] = c[i-1][j];11 if(w[i] <=
j)
12 {
13 if(c[i-
1][j-w[i]]+p[i] > c[i-
1][j])
14 c[i][j] = c[i-
1][j-w[i]] +
p[i];
15 else c[i][j] = c[i-
1][j];
16 }
17 else c[i][j] = c[i-
1][j];
18 }
19 return c[m][n];
20 }
21 int main ()
22 {
23 int t,i,m,n;
24 scanf(
"%d",&
t);
25
26
27 while(t--
)
28 {
29 scanf(
"%d %d",&m, &
n);
//有m件物品，容器最大容积为n30 for(i =
1; i <= m; i++
)
31 scanf(
"%d",&
p[i]);
//物品的价值32 for(i =
1; i<= m; i++
)
33 scanf(
"%d",&
w[i]);
//物品的体积。34 printf(
"%d\n",knaspack(m,n));
35 }
36 return 0;
37 }
也可以用一位数组
1 #include<stdio.h>
2 #include<
string.h>
3 int p[
1100],w[
1100],dp[
1100];
4 int main ()
5 {
6 int n,m,t;
7 scanf(
"%d",&
t);
8 while(t--
)
9 {
10 scanf(
"%d %d",&n,&
m);
11 for(
int i =
0; i < n; i++
)
12 scanf(
"%d",&
p[i]);
13 for(
int i =
0; i < n; i++
)
14 scanf(
"%d",&
w[i]);
15 memset(dp,
0,
sizeof(dp));
16 for(
int i =
0; i < n; i++
)
17 for(
int j = m;j >= w[i]; j--
)//体积按倒序
18 if(dp[j-w[i]]+p[i] >
dp[j])
19 dp[j] = dp[j-w[i]]+
p[i];
20 printf(
"%d\n",dp[m]);
21 }
22 return 0;
23
24 }
转载于:https://www.cnblogs.com/LK1994/archive/2013/05/02/3055091.html
相关资源：JAVA上百实例源码以及开源项目
