| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
输入的第 1 行，为两个正整数N，m，用一个空格隔开。其中 N 表示总钱数， m 为可购买的物品的个数。
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v、p、q。
其中 v 表示该物品的价格，p 表示该物品的重要度，q 表示该物品是主件还是附件。
如果 q=0，表示该物品为主件，如果q>0，表示该物品为附件， q 是所属主件的编号。
数据范围：N<32000，m<60，v<10000，1<=p<=5。
输出一个正整数，为张强可以获得的最大的满意度。
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
2200
50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0
130
由第1行可知总钱数N为50以及希望购买的物品个数m为5； 第2和第3行的q为5，说明它们都是编号为5的物品的附件； 第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5； 所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
import java.util.Scanner;
//加了限制条件的背包问题
public class Main {
public static int getMaxValue(int[] val, int[] weight, int[] q, int n, int w) {
int[][] dp = new int[n + 1][w + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (q[i-1] == 0) { // 主件
if (weight[i - 1] <= j) // 用j这么多钱去买 i 件商品 可以获得最大价值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j- weight[i - 1]]+ val[i - 1]);
}
else { //附件
if (weight[i - 1] + weight[q[i - 1]] <= j) //附件的话 加上主件一起算
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j- weight[i - 1]]+ val[i - 1]);
}
}
}
return dp[n][w];
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNextInt()) {
int n = input.nextInt(); // 总钱数
int m = input.nextInt(); // 商品个数
int[] p = new int[m];
int[] v = new int[m];
int[] q = new int[m];
for (int i = 0; i < m; i++) {
p[i] = input.nextInt(); // 价格
v[i] = input.nextInt() * p[i]; // 价值
q[i] = input.nextInt(); // 主or附件
}
System.out.println(getMaxValue(v, p, q, m, n));
}
}
}
money, things = map(int, input().split()) money = money // 10 # money都是10的整数，整除后，减小循环次数 # 三列分别表示主件，附件1，附件2 weight = [[0] * 3 for _ in range(0, things + 1)] # 价格 value = [[0] * 3 for _ in range(0, things + 1)] # 价值=价格*重要度 result = [[0] * (money + 1) for _ in range(0, things + 1)] for i in range(1, things + 1): prices, degree, depend = map(int, input().split()) # 分别为价格，重要性，主附件 prices = prices // 10 if depend == 0: # 主件 weight[i][0] = prices value[i][0] = prices * degree elif weight[depend][1] == 0: # 附件 weight[depend][1] = prices # 第一个附件 value[depend][1] = prices * degree else: weight[depend][2] = prices # 第二个附件 value[depend][2] = prices * degree # 遍历计算 for i in range(1, things + 1): # 每几件物品 for j in range(money, -1, -1): if j >= weight[i][0]: # 当前价格j可以容下第i个主件时,比较（上一个物品对应价格的价值）与（第i个物品的价值 + 余额价格对应上个物品价值） result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0]] + value[i][0]) # 在确定主件可容纳，并做相应计算之后,判断附件的容纳情况，如果主件都没有办法容纳，则附件必定不可容纳 if j >= (weight[i][0] + weight[i][1]): # 当可以容下第i个主件和此主件的第1个附件时，此时需要在比大小时加入当前最优，保证添加附件的结果不会反而更小 # 比较（当前价格对应上一物品的价值）与（主键价值+附件1价值+上一物品在价格（j-主键价格-附件1价格）时对应的价值） result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1]] + value[i][0] + value[i][1]) if j >= (weight[i][0] + weight[i][2]): # 可以容下第i个主件和此主件的第2个附件，此时也需要在比大小时加入当前最优，保证添加附件的结果不会反而更小 # 比较（当前价格对应上一物品的价值）与（主键价值+附件2价值+上一物品在价格（j-主键价格-附件2价格）时对应的价值）, result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][2]] + value[i][0] + value[i][2]) # 根据3件物品价格之和必然大于等于2件物品的规则，只有在能容纳主件和附件2时，才有判断全部容纳可能性的必要 if j >= (weight[i][0] + weight[i][1] + weight[i][2]): # 当判断通过，则判断当前值与上物品计算当前价格价值与当前3物品情况价值中最大值，同时还要比较目前最优值 result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + value[i][0] + value[i][1] + value[i][2]) else: # 当前价格j不能容下第i个主件时,价值为上一个物品的对应价格的价值 result[i][j] = result[i - 1][j] print(result[things][money] * 10)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Sixteen {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 总钱数
int N = scanner.nextInt();
// 购买物品个数
int m = scanner.nextInt();
int[] f = new int[N + 1];
// 分组，goods[i][0]为主件，goods[i][1]为附件1，goods[i][2]为附件2
Good[][] goods1= new Good[60][4];
for (int i = 1; i <= m; i++) {
int v = scanner.nextInt();
int p = scanner.nextInt();
int q = scanner.nextInt();
Good t = new Good(v, v * p);
if (q == 0) {
goods1[i][0] = t;
} else {
if (goods1[q][1] == null) {
goods1[q][1] = t;
} else {
goods1[q][2] = t;
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = N; j >= 0 && goods1[i][0] != null; j--) {
//以下代码从分组中选择价值最大的。共五种情况：不选主件，选主件，选附件1和主件，选附件2和主件，选附件1和附件2和主件
Good master = goods1[i][0];
int max = f[j];
if (j >= master.v && max < f[j - master.v] + master.vp) {
max = f[j - master.v] + master.vp;
}
int vt;
if (goods1[i][1] != null) {
if (j >= (vt = master.v + goods1[i][1].v)
&& max < f[j - vt] + master.vp + goods1[i][1].vp) {
max = f[j - vt] + master.vp + goods1[i][1].vp;
}
}
if (goods1[i][2] != null) {
if (j >= (vt = master.v + goods1[i][1].v + goods1[i][2].v)
&& max < f[j - vt] + master.vp + goods1[i][1].vp + goods1[i][2].vp) {
max = f[j - vt] + master.vp + goods1[i][1].vp + goods1[i][2].vp;
}
}
f[j] = max;
}
}
System.out.println(f[N]);
}
}
class Good {
int v;
int vp;
public Good(int v, int vp) {
this.v = v;
this.vp = vp;
}
}
有依赖的背包问题，参考http://blog.csdn.net/liang5630/article/details/8030108
转换为01背包
测试用例有问题 case通过率为80.00% 测试用例: 1738 55 20 3 0 50 2 0 120 3 0 40 3 0 100 4 0 220 2 0 40 2 0 200 3 0 90 3 0 10 3 0 230 2 0 300 1 0 70 2 0 270 1 0 300 3 0 70 5 0 300 2 0 200 1 0 210 1 0 270 2 0 180 2 0 40 2 0 110 4 0 170 4 0 110 1 0 280 4 0 50 4 0 160 2 0 10 3 0 320 3 0 10 5 0 50 2 0 230 4 0 230 1 0 150 5 0 160 5 0 90 5 0 140 3 0 140 3 0 250 5 0 330 2 0 190 3 0 230 1 0 70 2 0 50 3 0 170 5 0 100 5 0 230 5 0 120 1 0 70 2 0 50 3 0 240 1 0 220 1 0 20 5 0 20 3 0 对应输出应该为: 8090 你的输出为: 8160 #include <iostream> #include <algorithm> #define max(x,y) (x)>(y)?(x):(y) using namespace std; int main() { int N,m; //N 总钱数 m为购买物品个数 int weight[61][3]={0}; int value[61][3] = {0}; while(cin>>N>>m) { int dp[61][3201] = {0}; N /= 10; //都是10的整数倍 节约空间 int v,p,q; for(int i=1;i<=m;i++) { cin>>v>>p>>q; p = p*v; v /= 10; //按主件附件分类 第二个小标表示是第i件物品还是主件附件 if(q==0) { weight[i][q] = v; value[i][q] = p; } else if(weight[q][1]==0) { weight[q][1] = v; value[q][1] = p; } else { weight[q][2] = v; value[q][2] = p; } } //开始进行动态规划 for(int i=1;i<=m;i++) for(int j=1;j<=N;j++) { dp[i][j] = dp[i-1][j]; if(weight[i][0]<=j) { int t = max(dp[i-1][j],dp[i-1][j-weight[i][0]]+value[i][0]); if(t>dp[i][j]) dp[i][j] = t; } if(weight[i][0]+weight[i][1]<=j) { int t = dp[i-1][j-weight[i][0]-weight[i][1]]+value[i][0]+value[i][1]; if(t>dp[i][j]) dp[i][j] = t; } if(weight[i][0]+weight[i][2]<=j) { int t = dp[i-1][j-weight[i][0]-weight[i][2]]+value[i][0]+value[i][2]; if(t>dp[i][j]) dp[i][j] = t; } if(weight[i][0]+weight[i][1]+weight[i][2]<=j) { int t = dp[i-1][j-weight[i][0]-weight[i][1]-weight[i][2]]+value[i][0]+value[i][1]+value[i][2]; if(t>dp[i][j]) dp[i][j] = t; } } cout<<dp[m][N]<<endl; } return 0; }
#include <bits/stdc++.h>
using namespace std;
const int N = 100, M = 33000;
int v[N][3], c[N][3], f[M];
int n, m, cnt;
int main(){
while(scanf("%d%d", &m, &n) == 2){
memset(v, 0, sizeof(v[0]) * (n + 5));
memset(c, 0, sizeof(c[0]) * (n + 5));
memset(f, 0, sizeof(f[0]) * (m + 5));
for(int i = 1; i <= n; ++i){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if(z == 0) v[i][2] = x * y, c[i][2] = x;
else for(int j = 0; j <= 1; ++j) if(v[z][j] == 0) {
v[z][j] = x * y;
c[z][j] = x;
break;
}
}
for(int i = 1; i <= n; ++i){
for(int k = m; k >= 0; --k){
for(int s = 0; s < 4; ++s){
int val = v[i][2], cst = c[i][2];
for(int j = 0; j <= 1; ++j){
if(s & (1 << j)) val += v[i][j], cst += c[i][j];
}
if(cst <= k) f[k] = max(f[k], f[k - cst] + val);
}
}
}
printf("%d\n", f[m]);
}
return 0;
}
30 4 10 5 4 10 5 4 10 5 0 10 1 0答案是110，而不是150
N,M=3200,60 f=[0]*N #分组背包，每组有四种情况，a.主件 b.主件+附件1 c.主件+附件2 d.主件+附件1+附件2 v=[[0 for i in range(4)] for j in range(M)] #体积 w=[[0 for i in range(4)] for j in range(M)] #价值 n,m=map(int,input().split()) n=n//10#价格为10的整数倍，节省时间 for i in range(1,m+1): x,y,z=map(int,input().split()) x=x//10 if z==0: for t in range(4): v[i][t], w[i][t] = v[i][t]+x, w[i][t]+x* y elif v[z][1]==v[z][0]:#如果a==b，添加附件1(如果a=b=c=d说明没有附件) v[z][1],w[z][1] = v[z][1] + x, w[z][1] + x* y v[z][3],w[z][3] = v[z][3] + x, w[z][3] + x* y else:#添加附件2 v[z][2], w[z][2] = v[z][2] + x, w[z][2] + x* y v[z][3], w[z][3] = v[z][3] + x, w[z][3] + x* y for i in range(1,m+1): for j in range(n,-1,-1): for k in range(4): if j>=v[i][k]: f[j]=max(f[j],f[j-v[i][k]]+w[i][k]) print(10*f[n])我来发个答案吧，修改了好久终于通了。。。
#include <iostream>
#include <string>
using namespace std;
int getMax(int x, int y){
return (x > y ? x : y);
}
int main(){
int N; //总钱数
int m; //希望购买的物品个数
int weight[60][3]={0}; //价格（成本）
int value[60][3]={0}; //价值（重要度*价格）
int f[60][3200]; //第i个物品在j容量下可以获得的最大价值
int i,j;
cin >> N >> m;
N/=10; //都是10的整数，先除以10，减少循环次数
//存储清单
for(int i=1;i<=m;i++){
int v; //该物品价格
int p; //该物品价值
int q; //该物品主件还是附件
cin >> v >> p >> q;
v/=10;
if(q==0){ //主件
weight[i][0]=v;
value[i][0]=p*v;
}
else{ //附件
if(weight[i][1]==0){ //第一个附件
weight[i][1]=v;
value[i][1]=p*v;
}
else{ //第二个附件
weight[i][2]=v;
value[i][2]=p*v;
}
}
}
//遍历计算
for(i=1;i<=m;i++)
for(j=N;j>0;j--){
if(j>=weight[i][0]) //可以容下第i个主件时,比较放第i个或者不放第i个物品的价值
f[i][j]=getMax(f[i-1][j],f[i-1][j-weight[i][0]]+value[i][0]);
if(j>=weight[i][0]+weight[i][1]) //可以容下第i个主件和此主件的第1个附件时
f[i][j]=getMax(f[i-1][j],f[i-1][j-weight[i][0]-weight[i][1]]+value[i][0]+value[i][1]);
if(j>=weight[i][0]+weight[i][2]) //可以容下第i个主件和此主件的第2个附件时
f[i][j]=getMax(f[i-1][j],f[i-1][j-weight[i][0]-weight[i][2]]+value[i][0]+value[i][2]);
if(j>=weight[i][0]+weight[i][1]+weight[i][2]) //可以容下第i个主件和此主件的第1个附件和第2个附件时
f[i][j]=getMax(f[i-1][j],f[i-1][j-weight[i][0]-weight[i][1]-weight[i][2]]+value[i][0]+value[i][1]+value[i][2]);
}
cout << f[m][N]*10 << endl;
}
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int sum_money = 0;
int num = 0;
sum_money=sc.nextInt();
num=sc.nextInt();
int price[]=new int[num+1];
int val[]=new int[num+1];
int[] q = new int[num+1];
for (int i = 1; i <= num; i++) {
price[i]=sc.nextInt();
val[i]=sc.nextInt()*price[i];
q[i]=sc.nextInt();
}
int[][] dp=new int[num+1][sum_money+1];
/*
* 初始值java默认赋值为0,其中dp[0][0...sum_money]为0,从dp[1][0...sum_money]
计算第1行,代表第一件物品
dp[i][sum_money] ： 前i个物体放入容量为sum_money的背包的最大价值；
dp[i-1][sum_money] ： 前i-1个物体放入容量为sum_money的背包的最大价值；
dp[i-1][sum_money-price[i]] ： 前i-1个物体放入容量为sum_money-price[i]的背包的最大价值；
dp[i][sum_money]=Math.max{dp[i-1][sum_money-price[i]]+val[i] , dp[i-1][sum_money]}
*/
for (int i = 1; i <=num; i++) {
for (int j = 1; j <= sum_money; j++) {
if(q[i]==0)
{
if(price[i]<=j)
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-price[i]]+val[i]);
}
if(q[i]>0)
{
if(price[i]+price[q[i]]<=j)
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-price[i]-price[q[i]]]+val[i]+val[q[i]]);
}
}
}
System.out.println(dp[num][sum_money]);
}
}
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
int main()
{
int v[100]; //价格
int q[100]; //主件or附件
int vp[100]; //权重*价格
int dp[100][3000];
int N,m;
while(cin >> N >> m)
{
for(int i=0;i<100;i++)
memset(dp[i], 0, sizeof(dp[i]));
int tmpw; //临时变量用于保存权重
//初始化赋值
for(int i=1;i<=m;i++)
{
cin >> v[i] >> tmpw >> q[i];
vp[i] = v[i] * tmpw;
}
for(int i=1;i<=m;i++) //一共有m组数据
{
for(int j=1;j<=N;j++) //j为价格，从0到N进行遍历
{
if(q[i] == 0)
{
if(v[i]<=j) //如果j >= v[i]
{
dp[i][j] = max(dp[i-1][j-v[i]]+vp[i], dp[i-1][j]); //将上一行同列的元素值与 上一行同列减去v[i]加上vp[i]的值做比较
}else{
dp[i][j] = dp[i-1][j]; //复制上一行的数据
}
}
else
{
if(v[i] + v[q[i]] <= j) //判断条件需要j> (v[i] + v[q[i]])
{
dp[i][j] = max(dp[i-1][j-v[i]]+vp[i], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
}
cout << dp[m][N] << endl;
}
return 0;
}
2200400*3+500*2 =2200 ，为什么不是800*2+400*5=3600 呢(1主1附件) ， 1000*5> 3600 > 2000
n,m=map(int,input().split()) f=[0]*n #购物单总价值 #分组背包，每组有四种情况，a.主件 b.主件+附件1 c.主件+附件2 d.主件+附件1+附件2 v=[[0 for i in range(4)] for j in range(m+1)] #每组的资金 w=[[0 for i in range(4)] for j in range(m+1)] #每组的重要度 n=n//10#价格为10的整数倍，节省时间 for i in range(1,m+1): x,y,z=map(int,input().split()) x=x//10 if z==0: # 主件，同时给每个组合初始化主件的金额跟重要度 for t in range(4): v[i][t], w[i][t] = v[i][t]+x, w[i][t]+x* y elif v[z][1]==v[z][0]:#附件且a==b，意味着附件1没加入，这时候累加b跟d情况 v[z][1],w[z][1] = v[z][1] + x, w[z][1] + x* y v[z][3],w[z][3] = v[z][3] + x, w[z][3] + x* y else:#附件且a!=b，意味着附件1加入了附件2没加入，这时候累加c跟d情况 v[z][2], w[z][2] = v[z][2] + x, w[z][2] + x* y v[z][3], w[z][3] = v[z][3] + x, w[z][3] + x* y # m:加入购物单的物品个数上限 for i in range(1, m+1): # n:购物总资金上限，只能倒序遍历，因为背包的思维是可用空间从大到小，求当前每个子状态的最优， # 如果顺序遍历，背包容量变大，之前遍历的子状态的最优结论就被推翻了 for j in range(n, -1, -1): for k in range(4): if j >= v[i][k]: # 将每组的购物资金 整体视为 一个容量，这样才不会出现主件重复放入的情况，这也是其他答案犯错的地方 # f[j]：表示总花费为j钱时的最大购物价值 f[j] = max(f[j], f[j-v[i][k]]+w[i][k]) print(10*f[n])
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int money = in.nextInt();
int num = in.nextInt();
int[][] prices = new int[num + 1][3];
int[][] weights = new int[num + 1][3];
for (int i = 1; i <= num; i++) {
int price = in.nextInt();
int weight = in.nextInt();
int zfj = in.nextInt();
weight *= price;
if (zfj == 0) {
prices[i][0] = price;
weights[i][0] = weight;
} else if (prices[zfj][1] == 0) {
prices[zfj][1] = price;
weights[zfj][1] = weight;
} else {
prices[zfj][2] = price;
weights[zfj][2] = weight;
}
}
int[] dp = new int[money + 1];// dp数组
for (int i = 1; i <= num; i++) {// 遍历物品
for (int j = money; j >= 0; j -= 10) {// 遍历money
int a = j - prices[i][0];
int b = j - prices[i][0] - prices[i][1];
int c = j - prices[i][0] - prices[i][2];
int d = j - prices[i][0] - prices[i][1] - prices[i][2];
int e = weights[i][0];
int f = weights[i][0] + weights[i][1];
int g = weights[i][0] + weights[i][2];
int h = weights[i][0] + weights[i][1] + weights[i][2];
dp[j] = a >= 0 ? Math.max(dp[j], dp[a] + e) : dp[j];// 是否购买主件
dp[j] = b >= 0 ? Math.max(dp[j], dp[b] + f) : dp[j];// 是否购买主件和附件1
dp[j] = c >= 0 ? Math.max(dp[j], dp[c] + g) : dp[j];// 是否购买主件和附件2
dp[j] = d >= 0 ? Math.max(dp[j], dp[d] + h) : dp[j];// 是否购买主件和附件1和附件2
}
}
System.out.println(dp[money]);// 输出结果
}
} 
背包问题， 增加限定条件不影响 用dp。。。。
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
int main()
{
int v[61];
int dp[61][32001];
int q[61];
int vp[61];
int N,m;
while(cin >> N >> m)
{
for(int i=0;i<61;i++)
memset(dp[i], 0, sizeof(dp[i]));
int tmpw;
for(int i=1;i<=m;i++)
{
cin >> v[i] >> tmpw >> q[i];
vp[i] = v[i] * tmpw;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=N;j++)
{
if(q[i] == 0)
{
if(v[i]<=j)
{
dp[i][j] = max(dp[i-1][j-v[i]]+vp[i], dp[i-1][j]);
}
}
else
{
if(v[i] + v[q[i]] <= j)
{
dp[i][j] = max(dp[i-1][j-v[i]]+vp[i], dp[i-1][j]);
}
}
}
}
cout << dp[m][N] << endl;
}
return 0;
}
import java.util.Scanner;
import java.*;
public class Main{
public static void main(String[] args){
// 输入数据
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
Goods[] goods = new Goods[m+1];
for(int i=1; i<=m; i++){
int v = in.nextInt();
int p = in.nextInt();
int q = in.nextInt();
goods[i] = new Goods(v,p,q);
// 如果商品是附件
if(q > 0){
if(goods[q].addID1 == 0) goods[q].addID1 = i;
else goods[q].addID2 = i;
}
}
// 处理网格
int[][] dp = new int[m+1][n+1];
for(int i=1; i<=m; i++){ // 第 i 个商品
int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
int w1 = 0, w2 = 0, w3 = 0, w4 = 0;
// 1. 主件
v1 = goods[i].v;
w1 = v1*goods[i].p;
// 2. 主件 + 附件1
if(goods[i].addID1 != 0){
v2 = v1 + goods[goods[i].addID1].v;
w2 = w1 + goods[goods[i].addID1].v*goods[goods[i].addID1].p;
}
// 3. 主件 + 附件2
if(goods[i].addID2 != 0){
v3 = v1 + goods[goods[i].addID2].v;
w3 = w1 + goods[goods[i].addID2].v*goods[goods[i].addID2].p;
}
// 4. 主件 + 附件1 + 附件2
if(goods[i].addID1 != 0 && goods[i].addID2 !=0){
v4 = v2 + v3 - v1;
w4 = w2 + w3 - w1;
}
for(int j=1; j<=n; j++){
if(goods[i].q > 0) {
dp[i][j] = dp[i-1][j]; // 附件行数据 会跟它的 主件行数据 一模一样
continue; // 跳过附件
}
// 对于主件行数据而言，它需要考虑四种情况里，自己选择哪种能够利益最大化
dp[i][j] = dp[i-1][j];
if(v1 <= j) dp[i][j] = Math.max(dp[i][j], w1+dp[i-1][j-v1]);
if(v2 <= j && v2 != 0) dp[i][j] = Math.max(dp[i][j], w2+dp[i-1][j-v2]);
if(v3 <= j && v3 != 0) dp[i][j] = Math.max(dp[i][j], w3+dp[i-1][j-v3]);
if(v4 <= j && v4 != 0) dp[i][j] = Math.max(dp[i][j], w4+dp[i-1][j-v4]);
}
}
// 输出数据
System.out.println(dp[m][n]);
}
}
// 商品类
class Goods{
int v;
int p;
int q;
int addID1 = 0; // 附件1的ID
int addID2 = 0; // 附件2的ID
public Goods(int v, int p, int q){
this.v = v;
this.p = p;
this.q = q;
}
} ''' 01背包问题 题意：所有的物品都分为两类，一类是主件，另一类是附件，附件有附件1和附件2 其中，每一个附件都有它的主件，选取它的主件之后才能选取附件 在取某件物品时，我们只需要从以下四种方案中取最大的那种方案： 1.只取主件 2.取主件＋附件1 3.取主件＋附件2 4.既主件＋附件1＋附件2。很容易得到如下状态转移方程： f[i,j]=max(f[i-1,j]) f[i-1,j-a[i,0]]+a[i,0]*b[i,0] f[i-1,j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1] f[i-1,j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2] f[i-1,j-a[i,0]-a[i,1]-a[i,2]]+a[i,0]*b[i,0]+a[i,1]*b[i,1]+a[i,2]*b[i,2] 含义: f[i,j]表示用j元钱，买第i类物品，所得的最大价值 a[i,0]表示第i类物品主件的价格 a[i,1]表示第i类物品第1个附件的价格 a[i,2]表示第i类物品第2个附件的价格 b[i,0],b[i,1],b[i,2]分别表示主件、第1个附件和第2个附件的重要度。 需要在满足金额money内，买到最大价值的物品。价值=价格*重要度 ''' money, things = map(int, input().split()) money = money // 10 #money都是10的整数，整除后，减小循环次数 #三列分别表示主件，附件1，附件2 weight = [[0] * 3 for _ in range(0, things + 1)] #价格 value = [[0] * 3 for _ in range(0, things + 1)] #价值=价格*重要度 result = [[0] * (money + 1) for _ in range(things + 1)] for i in range(1, things + 1): prices, degree, depend = map(int, input().split()) #分别为价格，重要性，主附件 prices = prices // 10 if depend == 0: #主件 weight[i][0] = prices value[i][0] = prices * degree elif weight[depend][1] == 0: #附件 weight[depend][1] = prices #第一个附件 value[depend][1] = prices * degree else: weight[depend][2] = prices #第二个附件 value[depend][2] = prices * degree #遍历计算 for i in range(1, things + 1): for j in range(money, 9, -10): if j >= weight[i][0]: #可以容下第i个主件时,比较不放第i个或者放第i个物品的价值 result[i][j] = max(result[i - 1][i], result[i - 1][j - weight[i][0]] + value[i][0]) else: result[i][j] = result[i - 1][j] if j >= (weight[i][0] + weight[i][1]): #可以容下第i个主件和此主件的第1个附件时 result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1]] + value[i][0] + value[i][1]) else: result[i][j] = result[i - 1][j] if j >= (weight[i][0] + weight[i][2]): #可以容下第i个主件和此主件的第2个附件时 result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][2]] + value[i][0] + value[i][2]) else: result[i][j] = result[i - 1][j] if j >= (weight[i][0] + weight[i][1] + weight[i][2]): #可以容下第i个主件和此主件的第1个附件和第2个附件时 result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + value[i][0] + value[i][1] + value[i][2]) else: result[i][j] = result[i - 1][j] print(result[things][money] * 10) --------------------- 作者：萝卜luo 来源：CSDN 原文：https://blog.csdn.net/luohaobo/article/details/92852970 版权声明：本文为博主原创文章，转载请附上博文链接！
n, m = map(int, input().split()) prices = [0] * m degree = [0] * m depend = [0] * m # 在这里记录的主件下标是从1开始的 for i in range(m): prices[i], degree[i], depend[i] = map(int, input().split()) result = [[0] * (n + 1) for i in range(m + 1)] for i in range(1, m + 1): # 选择商品 for j in range(10, n + 1, 10): # 价格（10的整数） if depend[i - 1] == 0: # 如果为主件 if prices[i - 1] <= j: result[i][j] = max(result[i - 1][j], result[i - 1][j - prices[i - 1]] + prices[i - 1] * degree[i - 1]) elif prices[i - 1] + prices[depend[i - 1] - 1] <= j: # 如果为配件，钱比配件大；然后比较加与不加谁大（空出主件＋该配件的钱，然后加上主件和配件与重要度的乘积） result[i][j] = max(result[i - 1][j], result[i - 1][j - prices[i - 1] - prices[depend[i - 1] - 1]] + prices[i - 1] * degree[ i - 1] + prices[depend[i - 1] - 1] * degree[depend[i - 1] - 1]) print(result[m][int(n / 10) * 10]) # n可能非10的倍数 --------------------- 来源：牛客网讨论区
while True:
try:
total_money,total_num=map(int,input().split(' '))
total_money//=10
product_item=[]
for i in range(total_num):
v,p,q=map(int,input().split(' '))
v//=10
product_item+=[[i+1,v,p,q]]
dp=[[0,[0]] for i in range(total_money+1)]
for current_no,v,p,q in product_item:
for i in range(len(dp)-1,-1,-1):
if (i-v)>=0:
if not current_no in dp[i-v][1]:
if q in dp[i-v][1]: # the parent has been chosen.
if (dp[i-v][0]+v*p)>dp[i][0]:
dp[i][0]=dp[i-v][0]+v*p
dp[i][1]=dp[i-v][1].copy()
dp[i][1]+=[current_no]
else: # the parent has not been chosen, then we can pick up both current one and the parent.
if (i-v-product_item[q-1][1])>0:
if (dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2])>dp[i][0] and not current_no in dp[i-v-product_item[q-1][1]][1] and not q in dp[i-v-product_item[q-1][1]][1]:
dp[i][0]=dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2]
dp[i][1]=dp[i-v-product_item[q-1][1]][1].copy()
dp[i][1]+=[current_no]
dp[i][1]+=[q]
print(dp[total_money][0]*10)
except:
break 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
