南通优化网站费用,安康网站建设,网站解决方案,丰镇网站建设有 NN 种物品和一个容量是 VV 的背包#xff0c;每种物品都有无限件可用。
第 ii 种物品的体积是 vivi#xff0c;价值是 wiwi。
求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值。
输入格式
第一行两个整…有 NN 种物品和一个容量是 VV 的背包每种物品都有无限件可用。
第 ii 种物品的体积是 vivi价值是 wiwi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式
第一行两个整数NVNV用空格隔开分别表示物品种数和背包容积。
接下来有 NN 行每行两个整数 vi,wivi,wi用空格隔开分别表示第 ii 种物品的体积和价值。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤10000N,V≤1000 0vi,wi≤10000vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例
10
思路
dp[i]表示体积小于i的所有方案中的价值最大值 提交的代码
import java.util.Scanner;
public class Main { public static void main(String[] args) { int m,n; Scanner sc new Scanner(System.in); m sc.nextInt();//物品数量 n sc.nextInt();//背包容量 int i,j; int dp[] new int[n1]; int weight[] new int[m1]; int value[] new int[m1]; for(i1;im;i) { weight[i] sc.nextInt(); value[i] sc.nextInt(); } for(i1;im;i) { for(jweight[i];jn;j) //例如现在物品的体积为3dp[3]max(dp[3], dp[0]value[i]),dp[6]max(dp[6], dp[3]value[i]) //dp[9]max(dp[9], dp[6]value[i]),所以同一物品选取多次的情况已经考虑到了 { dp[j]Math.max(dp[j], dp[j-weight[i]]value[i]); } } System.out.println(dp[n]); } }
