人生第一题洛谷绿题必须记录一下
题目：P1064 [NOIP 2006 提高组] 金明的预算方案 - 洛谷
AC记录：
大致思路
这题看一眼就知道是01背包变种，但是怎么处理依赖关系是头等问题。由题目知物品分为主件和附件，附件不能单独存在，每个主件最多可以有2个附件，那我们就写个结构体来存每个主件和他的附件如下图
v1代表主件需要花费多少 v2代表第一个附件花费多少
那s是什么？
题中有个条件：设第 j 件物品的价格为 vj，重要度为 wj，共选中了 k 件物品，编号依次为 j1,j2,…,jk，则所求的总和为：
vj1×wj1+vj2×wj2+⋯+vjk×wjk
什么意思意思解释当前物品的价值等于他的v*w=s言简意赅
读入输入流
Scanner sc = new Scanner(System.in);
int sum = sc.nextInt();
int n = sc.nextInt();
sp[] sp = new sp[n+1];
for(int i=1;i<=n;i++){
int v=sc.nextInt(),p=sc.nextInt(),q=sc.nextInt();
sp[i] = new sp();
if(q==0){
sp[i].v1=v;
sp[i].s1=v*p;
}else{
if(sp[q].v2==0){
sp[q].v2=v;
sp[q].s2=v*p;
}else{
sp[q].v3=v;
sp[q].s3=v*p;
}
}
}
注意我这里有个错误导致后面额外测试点re两个，细心的你一定能发现（我没有考虑万一附件比主件出现的早怎么办！！！）
模板
做这题你必须了解最基本的背包问题你要是不会我建议可以先解决 P1048 [NOIP2005 普及组] 采药（01 背包模板题）不多解释上模板
可以先解决 P1048 [NOIP2005 普及组] 采药（01 背包模板题）不多解释上模板
int[]dp = new int[sumV+1];
for(int i=1;i<=cnt;i++){
for(int j=sumV;j>=0;j--){
if(j>=v[i]){
dp[j] = Math.max(dp[j],dp[j-v[i]]+s[i]);
}
}
}
变种
首先我们就当只有主件那是不是直接变种成这样就行了其他都不用改
if(j>=sp[i].v1)
dp[j] = Math.max(dp[j],dp[j-sp[i].v1]+sp[i].s1);这时我们可以知道附件和主件只能同时出现是不是只能出现以下几种情况
1.v1+v2
2.v1+v3
3.v1+v2 +v3
加上之前的只考虑主件，发现好像就这些情况不多说直接上代码
for(int j=sum;j>=0;j--){
if(j>=sp[i].v1)
dp[j] = Math.max(dp[j],dp[j-sp[i].v1]+sp[i].s1);
if(j>=sp[i].v1+sp[i].v2)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2)]+sp[i].s1+sp[i].s2);
if(j>=sp[i].v1+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v3)]+sp[i].s1+sp[i].s3);
if(j>=sp[i].v1+sp[i].v2+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2+sp[i].v3)]+sp[i].s1+sp[i].s3+sp[i].s2);
}细心的你一定会发现有些i可能是附件附件是不可能有附件的那怎么办，直接跳过v1=0就可以啦
int[] dp = new int[sum+1];
for(int i=1;i<=n;i++){
if(sp[i].v1==0)continue;
for(int j=sum;j>=0;j--){
if(j>=sp[i].v1)
dp[j] = Math.max(dp[j],dp[j-sp[i].v1]+sp[i].s1);
if(j>=sp[i].v1+sp[i].v2)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2)]+sp[i].s1+sp[i].s2);
if(j>=sp[i].v1+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v3)]+sp[i].s1+sp[i].s3);
if(j>=sp[i].v1+sp[i].v2+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2+sp[i].v3)]+sp[i].s1+sp[i].s3+sp[i].s2);
}
}
附上完整代码
import java.util.Scanner;
public class 金明的预算方案 {
public static class sp {
int v1=0,v2=0,v3=0;
int s1=0,s2=0,s3=0;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int sum = sc.nextInt();
int n = sc.nextInt();
sp[] sp = new sp[n+1];
for(int i=1;i<=n;i++)sp[i] = new sp();
for(int i=1;i<=n;i++){
int v=sc.nextInt(),p=sc.nextInt(),q=sc.nextInt();
if(q==0){
sp[i].v1=v;
sp[i].s1=v*p;
}else{
if(sp[q].v2==0){
sp[q].v2=v;
sp[q].s2=v*p;
}else{
sp[q].v3=v;
sp[q].s3=v*p;
}
}
}
int[] dp = new int[sum+1];
for(int i=1;i<=n;i++){
if(sp[i].v1==0)continue;
for(int j=sum;j>=0;j--){
if(j>=sp[i].v1)
dp[j] = Math.max(dp[j],dp[j-sp[i].v1]+sp[i].s1);
if(j>=sp[i].v1+sp[i].v2)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2)]+sp[i].s1+sp[i].s2);
if(j>=sp[i].v1+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v3)]+sp[i].s1+sp[i].s3);
if(j>=sp[i].v1+sp[i].v2+sp[i].v3)
dp[j] = Math.max(dp[j],dp[j-(sp[i].v1+sp[i].v2+sp[i].v3)]+sp[i].s1+sp[i].s3+sp[i].s2);
}
}
System.out.println(dp[sum]);
}
}
完结撒花！！！！
人生第一题洛谷绿题必须记录一下
http://blog.zheco68.asia/archives/ren-sheng-di-yi-dao-luo-gu-lu-ti-bi-xu-ji-lu-yi-xia