完全背包思想 画图就明白

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class a8 {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner=new Scanner(System.in);

int a[]=new int[10+1];

for (int i = 1; i < a.length; i++) {

a[i]=scanner.nextInt();

}

int n=scanner.nextInt();

int dp[][]=new int [10+1][n+1];

for (int i = 1; i<a.length; i++) {

for (int j = 1; j<=n; j++) {

if (i==1) {

dp[i][j]=Math.max(dp[i-1][j], dp[i][j-i]+a[i]);

}

else {

if(i<=j){

dp[i][j]=Math.min(dp[i-1][j], dp[i][j-i]+a[i]);

}

else {

dp[i][j]=dp[i-1][j];

}

}

}

}

System.out.println(dp[10][n]);

}

}