购物单

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));
		}
	}
}

有依赖的背包问题，参考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

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;
}

首先应该明确示例的定义，示例对于理解题目来说非常关键
输入第一行，1000 是总预算（total_budget） 5 指总的物品数量（包含主件附件）
第二行之后的就是每个物品的描述数据了
第一列800 400 300 400 500 这些表示物品价格，第二列的数字是物品的重要度
第三列很关键，，非0 数字都表示这个物品是附件，0 表示这个物品是主件。
非0的同时这个数字是和主件有绑定关系的，比如是1，表示这个是主件1 的附件，那么主件1 是谁就很关键，
找错主件结果就完全不对了，所以这里要考虑我们在存储主件的时候，同时要保留的是主件的索引，从题目中来看，主件从1 开始
所以遇到第1行是0 的数据，就得更新主件索引为1（i + 1），同时将附件数据绑定上去，这样算是成功了一半了。

多重背包很关键的一点考虑在物品不能重复购买，这就说明你在预算计算的时候，需要考虑是倒序遍历
必须的，不然重复计算了，这点可能比较难理解，可以带入一下就能想的比较清晰，还有一点就是遍历时的stop 点
v - 1 , 当j >= v 的时候进行遍历即可
思考，先从主件开始，主件+附件1 主件+附件2 主件+附件1+附件2，依次更新dp[j]

#购物单 这是一个多重背包问题,购买主件后，可以不购买附件，也可以购买1件或者2件附件，不能重复购买，求最大的满意度
#首先定义这个输入输出
'''
1000 总预算 5物品数量
800 2 满意度 0 主件0
400 5 1 主件0 的附件1
300 5 1 主件0 的附件2
400 3 0 主件1
500 2 0 主件2
'''
import sys
total_budget, num_items = map(int, sys.stdin.readline().rstrip().split())

#存储主件
main_items = []
attachments = {}
i = 0
while i < num_items:
    v, p, q = map(int, sys.stdin.readline().rstrip().split())
    if q == 0: #存储主件
        main_items.append((v, p, i + 1))
    else: #附件
        if q not in attachments:
            attachments[q] = []
        attachments[q].append((v, p))
    i += 1

dp = [0] * (total_budget + 1)
#选择主件
for  v, p, idx in main_items:
    #从后往前遍历，避免重复选择
    for j in range(total_budget, v - 1, -1):
        dp[j] = max(dp[j], dp[j - v] + v * p)
        #计算附件
        if idx in attachments:
            for av, ap in attachments[idx]:
                if j >= v + av:
                    dp[j] = max(dp[j], dp[j - v - av] + v * p + av * ap)
            if len(attachments[idx]) == 2:
                av1, ap1 = attachments[idx][0]
                av2, ap2 = attachments[idx][1]
                if j >= av1 + av2 + v:
                    dp[j] = max(dp[j], dp[j - v - av1 - av2] + v * p + av1 * ap1 + av2 * ap2)

print(dp[total_budget])

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;
}

'''
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的倍数
---------------------
来源：牛客网讨论区