andy6804tw
11/3/2016 - 4:02 AM

## http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=33324

``````import java.util.Scanner;
public class Main
{
static int[][] c;
static int[] cost,weight;
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int test=sc.nextInt();
while(test-->0)
{
int N=sc.nextInt(),ans=0;
c=new int[1001][31];
cost=new int[N+1];
weight=new int[N+1];
for(int i=1;i<N+1;++i)
{
cost[i]=sc.nextInt();
weight[i]=sc.nextInt();
}
int G=sc.nextInt();
int[] pack=new int[G+1];
for(int i=1;i<G+1;++i)
pack[i]=sc.nextInt();
for(int i=1;i<G+1;++i)
ans+=knapsack(N,pack[i]);
System.out.println(ans);
}
}

public static int knapsack(int n, int w)
{
if (w<0)
return -100000;
if (n==0)
return 0;
if (c[n][w]!=0)
return c[n][w];
return c[n][w]=Math.max(knapsack(n-1, w-weight[n])+cost[n], knapsack(n-1, w));
}
}
``````
``````#include<stdio.h>
#include<stdlib.h>
int cost[1000], weight[1000];
int c[10000];
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(c, 0, sizeof(c));
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&cost[i],&weight[i]);
}
int g,w,tot=0;
scanf("%d",&g);
for(i=0;i<g;i++){
scanf("%d",&w);
tot+=knapsack(n, w);
}
printf("%d\n",tot);
}

system("PAUSE");
return 0;
}
int knapsack(int n, int w)
{

int k=0;
for(;k<10000;k++)
c[k]=0;
int i,j;
for (i = 0; i < n; ++i)
for (j = w; j - weight[i] >= 0; --j) {
// 由後往前
if(c[j]< c[j - weight[i]] + cost[i])
c[j]= c[j - weight[i]] + cost[i];
}
return c[w];
}``````